dijkstra
- Compute the distance between one node and all the other nodes of a weighted graph
dijkstra
graph_in node
dijkstra
computes the distance (and the shortest paths) between a
given node and all the other nodes of an undirected weighted graph
provided as input. The program implements the Dijkstra's algorithm.
-
(dash), read the edge list
from STDIN.dijkstra
prints on the standard output the distances betwen node
and all the other nodes of the graph, in the format:
d0 d1 d2 d3.....
where d0
is the distance to node 0
, d1
is the distance to node
1
, and so forth.
The following command:
$ dijkstra US_airports.net 0
0 4784 5662 6603 11097 7470 4472 ....
$
will show on output the distances between node 0 and all the other
nodes in the graph US_airports.net
(the US air transportation
network).
shortest(1)
E. W. Dijkstra. "A Note on Two Problems in Connexion with Graphs". Num. Math. 1 (1959), 269-271.
V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Chapter 10, Cambridge University Press (2017)
V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Appendix 6, Cambridge University Press (2017)
(c) Vincenzo 'KatolaZ' Nicosia 2009-2017 <v.nicosia@qmul.ac.uk>
.