Dijkstra's Algorithm

Author

Eric W. Weisstein
May 31, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/DijkstrasAlgorithm.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/DijkstrasAlgorithm.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Initialization

<<GraphUtilities`

Comparison

10 nodes

SeedRandom[1];
g=RandomGraph[10,.2]

Dijkstra[g,1]

SparseArray`ShortestPath[g,1]

SparseArray`ShortestPath[ToAdjacencyMatrix[g],1]

1000 nodes

SeedRandom[1];
(g=RandomGraph[1000,.2])//Timing

Dijkstra[g,1];//Timing

SparseArray`ShortestPath[ToAdjacencyMatrix[g],1];//Timing