Uses Dijkstra's algorithm
to find the shortest paths to each node,
showing the shortest distance from node 1
to every node, and the path itself.
The nodes must be numbered consecutively, from 1 (or 0)
to last node. If the initial node is 0, then 1 is added to all the nodes,
becoming 1..'nodes'.
The computation is based on a code version adapted by
J. Burkardt [2010].
The base problem is from T. Cormen [2014],
at lecture 20 (=.pdf)
giving 0 5 8 4 7 (i.e., distance from node 1 to node 3 is 8, etc.).
Draws a simple plot, just for the (already shown) values
of the shortest distances.
Other suggested data:
1 2 40, 1 3 15, 2 1 40, 2 3 20, 2 4 10, 2 5 25, 2 6 6,
3 1 15, 3 2 20, 3 4 100, 4 2 10, 4 3 100,
5 2 25, 5 6 8, 6 2 6, 6 5 8 (copy, paste, giving: 0 35 15 45 49 41);
1 2 4, 1 3 2, 2 4 1, 2 5 2, 3 2 1, 3 4 3, 3 5 4, 4 5 1
(giving: 0 3 2 4 5 ([Eiselt & Sandblom, 2000, p 293])).
Also, see 'GeeksExa.pdf' (below). |
|
• Burkardt, John,
2010, Dijkstra.
• Cormen, Thomas H.,
2014, Lecture 20, Dartmouth College
(Computer Science).
• Ikeda, Kenji,
Shortest Path Problem (home, Tokushima University).
• Shortest Paths
(by Sedgewick & Wayne, Princeton) • Dijkstra's algorithm.pdf (Melissa Yan, Math MIT; more)
• Animation: Dijkstra Shortest Paths (by David Galles, USFCA) (browser dependent ?)
• Some graph algorithms.pdf (Carol Ash, UIUC).
• GeeksforGeeks: Printing Paths in Dijkstra’s Shortest Path Algorithm (GeeksExa.pdf).
• Eiselt, H. A.,
C.-L. Sandblom, 2000,
"Integre programming and network models", Springer-Verlag, Berlin (Germany).
ISBN 3-54067191-9).
• Search Dijkstra's
algorithm
• 1781-06-21:
Poisson, Siméon Denis (1840-04-25). |
