How did Dijkstra's reach to single source shortest path algorithm?

Started by networkloser, July 14, 2025, 02:19:34 AM

Previous topic - Next topic

networkloser

Is there a history of attempts to write a shortest path algorithms? And how they failed? What was their thinking process. I am currently learning about link-state routing and I am unable to figure out centralized dijkstra's algorithm even after being stuck in screen/textbook for lots of hours. It is extremely overwhelming to me. Thus, if I could get ideas on why the algorithm was exactly made, why was it chosen for routing purposes, and stuffs like that, that'd greatly be of benefit to me.

deanwebb

To find the answer, I found this: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

And it's a fun little article about how Dijkstra thought it all out and made the algorithm. There is a step-by-step calculation that runs until one of the calculated paths reaches the destination. That first path is therefore the shortest.

The algorithm also works, with modifications, to present ranked-choice alternatives to the shortest path, should it become unavailable or degraded.

Other shortest-path solutions are discussed here: https://en.wikipedia.org/wiki/Shortest_path_problem . Solutions don't necessarily fail, but are rather perhaps better for some applications than others.
Take a baseball bat and trash all the routers, shout out "IT'S A NETWORK PROBLEM NOW, SUCKERS!" and then peel out of the parking lot in your Ferrari.
"The world could perish if people only worked on things that were easy to handle." -- Vladimir Savchenko
Вопросы есть? Вопросов нет! | BCEB: Belkin Certified Expert Baffler | "Plan B is Plan A with an element of panic." -- John Clarke
Accounting is architecture, remember that!
Air gaps are high-latency Internet connections.