Prof Bill Buchanan OBE FRSE’s Post

View profile for Prof Bill Buchanan OBE FRSE, graphic

Old World Breaker, New World Creator

In 1956, Edgar Dijkstra defined a way to find the best route through a graph - Dijksta's algorithm. We have since built the Internet on this foundation. Now researchers have actually shown that it's "universally optimal" https://lnkd.in/eyRdJFfh

I believe that Dijkstra said he wrote the algorithm in about 15 minutes whilst sitting outside a coffee shop one day. Genius.

Raed Addala

Junior Software Engineer

1mo

Where can I find a formal proof for the algorithm's complexity and optimality. Also are there any proofs that this is the best complexity we can reach (like in the case of other algorithms such as sorting algorithms, where we know we have reached the limit)

Shaurya Pratap Singh

Working @ DRDO || ICPC Regionalist 23 || Web Developer(MERN) || Quantum Computing (Qiskit)

1mo

Very informative

Mat Gardam

Cyber Defence and Information Assurance at Cranfield University

1mo

Interesting ... but sometimes the shortest route is neither the most efficient or quickest.

Charles Lindsey

Principal Data Scientist at Revionics

1mo

is anyone working with the weakest precondition stuff he did, that was fascinating

Wim Barthier

Security Officer at European Central Bank (cyber security, privacy, legislation, ...)

1mo

One of the greatest inventions of modern age and probably in the future as well! Beltug-NoCode-X-HOWEST University of Applied Sciences

Hassan Syed

Encryption Specialist (Reverse Engineer)

1mo

I believe, past generations were more intelligent than the present era people. This could also be because of less distractions in the past than now

Elfatih Ahmed

Group Head of IT, IT Director ,CIO,CTO | Driving Digital Transformation & Innovation | Strategic Technology Leader

1mo

This is the core of my Bsc thesis ,to find the shortest path (SPF) . Now ,is it possible to find a way to implement it on decentralised concepts? Which I beleive it can enhance the private blockchain performance i.e Hyperledger Fabric, or Besu...etc ?

Bruno Coutinho

Researcher at the Portuguese Institute of Telecommunications working on quantum networking and quantum computation

1mo

Interestingly, a multi-objective variation of the algorithm exists where distance is represented not by a single number but by a set of values. While a similar approach to Dijkstra (Martin's algorithm) can still be used to address this problem, it no longer guarantees a polynomial runtime. I actually used Martin's algorithm (or a generelized version of it) in my work.

Like
Reply
David W.

Building Smart AI Solutions | Project Leadership & Delivery | AI Research

1mo

I compared Dijkstra with A* recently. If the goal is optimal search performance, A* is worth considering. While Dijkstra’s algorithm is an uninformed search, A* uses a (admissible) heuristic for informed searching, making it more efficient by visiting fewer nodes to find the shortest path at the same cost. This has been explored in studies like Rachmawati and Gustin (2020).

See more comments

To view or add a comment, sign in

Explore topics