May 2017
Intermediate to advanced
310 pages
8h 5m
English
Content preview from Python Data Structures and Algorithms
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
Start your free trial
Dijkstra's shortest path algorithm
We introduce and study Dijkstra's algorithm. This algorithm is an example of a greedy algorithm. It finds the shortest distance from a source to all other nodes or vertices in a graph. By the end of this section, you will come to understand why it is classified as a greedy algorithm.
Consider the following graph:
By inspection, the first answer to the question of finding the shortest path between node A and node D that comes to mind is the edge with value or distance 9. From the diagram, it would seem that the straight path from node A to D would also yield the shortest route between the two nodes. But the ...