Find Shortest Paths Between All Nodes in a Directed Graph

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.

allShortestPaths(x)
extractPath(obj, start, end)

Arguments

x

matrix or distance object

obj

return value of allShortestPaths

start

integer, starting point of path

end

integer, end point of path

Details

If 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 NA or 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. Alternatively, x can be a distance object as returned by dist (corresponding to an undirected graph).

Value

allShortestPaths returns a list with components

length

A matrix with the total lengths of the shortest path between each pair of points.

middlePoints

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.

extractPath returns a vector of node numbers giving with the shortest path between two points.

References

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

Author

Friedrich Leisch

Examples

## 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)
#>      [,1] [,2] [,3] [,4] [,5]
#> [1,]    0   30   10   NA   NA
#> [2,]   NA    0   NA   70   40
#> [3,]   NA   NA    0   50   20
#> [4,]   NA   NA   NA    0   60
#> [5,]   NA   NA   NA   10    0

## compute all path lengths
z <- allShortestPaths(x)
print(z)
#> $length
#>      [,1] [,2] [,3] [,4] [,5]
#> [1,]    0   30   10   40   30
#> [2,]   NA    0   NA   50   40
#> [3,]   NA   NA    0   30   20
#> [4,]   NA   NA   NA    0   60
#> [5,]   NA   NA   NA   10    0
#> 
#> $middlePoints
#>      [,1] [,2] [,3] [,4] [,5]
#> [1,]    0    0    0    5    3
#> [2,]    0    0    0    5    0
#> [3,]    0    0    0    5    0
#> [4,]    0    0    0    0    0
#> [5,]    0    0    0    0    0
#> 

## the following should give 1 -> 3 -> 5 -> 4
extractPath(z, 1, 4)
#> [1] 1 3 5 4