Editorial/Data Protection
Shortest Paths

The functions that calculate shortest paths make use of two algorithms:

Algorithm   Application
Dijkstra for graphs without edges with negative weights
FiFo for graphs without cycles with negative length

Implemented are the following functions:

Function   Short Description
ShortestPathFromOneToOne shortest path between two vertices
ShortestPathsFromOneToAll shortest paths to all other vertices
ShortestPathsFromAllToOne shortest paths from all other vertices
ShortestPathsFromAllToAll shortest paths between all vertices

The facing column contains an example for ShortestPathsFromAllToOne.

graph in matrix form

{{1, 4, 7}, {2, 4, 7}, {3, 4, 7}, {4, 7}, {5, 4, 7}, {6, 1, 4, 7}, {7}}

plot shortest paths

Editorial/Data Protection • page checked on Nov. 28th 2005