allShortestPaths finds all shortest paths in a directed (or
undirected) graph using Floyd's algorithm.
extractPath can be
used to actually extract the path between a given pair of nodes.
matrix or distance object
return value of
integer, starting point of path
integer, end point of path
x is a matrix, then
x[i,j] has to be the length of the
direct path from point
i to point
j. If no direct
connection from point
i to point
j exist, then
x[i,j] should be either
Inf. Note that the
graph can be directed, hence
x[i,j] need not be the same as
x[j,i]. The main diagonal of
x is ignored.
x can be a distance object as returned by
dist (corresponding to an undirected graph).
allShortestPaths returns a list with components
A matrix with the total lengths of the shortest path between each pair of points.
A matrix giving a point in the middle of each
shortest path (or 0 if the direct connection is the shortest path),
this is mainly used as input for
extractPath returns a vector of node numbers giving with the
shortest path between two points.
Kumar, V., Grama, A., Gupta, A. and Karypis, G. Introduction to Parallel Programming - Design and Analysis of Algorithms, Benjamin Cummings Publishing, 1994, ISBN 0-8053-3170-0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
## build a graph with 5 nodes x <- matrix(NA, 5, 5) diag(x) <- 0 x[1,2] <- 30; x[1,3] <- 10 x[2,4] <- 70; x[2,5] <- 40 x[3,4] <- 50; x[3,5] <- 20 x[4,5] <- 60 x[5,4] <- 10 print(x) ## compute all path lengths z <- allShortestPaths(x) print(z) ## the following should give 1 -> 3 -> 5 -> 4 extractPath(z, 1, 4)