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
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)
Very informative
Interesting ... but sometimes the shortest route is neither the most efficient or quickest.
is anyone working with the weakest precondition stuff he did, that was fascinating
One of the greatest inventions of modern age and probably in the future as well! Beltug-NoCode-X-HOWEST University of Applied Sciences
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
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 ?
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.
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).
I believe that Dijkstra said he wrote the algorithm in about 15 minutes whilst sitting outside a coffee shop one day. Genius.