# Find Shortest Paths Between All Nodes in a Directed Graph

### Description

`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.

### Usage

1 2 | ```
allShortestPaths(x)
extractPath(obj, start, end)
``` |

### Arguments

`x` |
matrix or distance object |

`obj` |
return value of |

`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`

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

### Author(s)

Friedrich Leisch

### 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

### Examples

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)
``` |