# shortest.paths

##### Shortest (directed or undirected) paths between vertices

`shortest.paths`

calculates the length of all the
shortest paths from or to the vertices in the
network. `get.shortest.paths`

calculates one shortest path (the
path itself, and not just its length) from or to the given vertex.

- Keywords
- graphs

##### Usage

```
shortest.paths(graph, v=V(graph), mode = c("all", "out", "in"),
weights = NULL, algorithm = c("automatic", "unweighted",
"dijkstra", "bellman-ford",
"johnson"))
get.shortest.paths(graph, from, to=V(graph), mode = c("all", "out",
"in"), weights = NULL)
get.all.shortest.paths(graph, from, to = V(graph), mode = c("all", "out", "in"))
average.path.length(graph, directed=TRUE, unconnected=TRUE)
path.length.hist (graph, directed = TRUE, verbose = igraph.par("verbose"))
```

##### Arguments

- graph
- The graph to work on.
- v
- Numeric vector, the vertices from or to which the shortest paths will be calculated.
- mode
- Character constant, gives whether the shortest paths to or
from the given vertices should be calculated for directed graphs. If
`out`

then the shortest paths*from*the vertex, if`in`

then*to*it will be c - weights
- Possibly a numeric vector giving edge weights. If this
is
`NULL`

and the graph has a`weight`

edge attribute, then the attribute is used. If this is`NA`

then no weights are used (even if the graph has a - algorithm
- Which algorithm to use for the calculation. By default igraph tries to select the fastest suitable algorithm. If there are no weights, then an unweighted breadth-first search is used, otherwise if all weights are positive, then Dijkstra's algo
- from
- Numeric constant, the vertex from or to the shortest paths will be calculated. Note that right now this is not a vector of vertex ids, but only a single vertex.
- to
- Numeric vector, only the shortest paths to these vertices will be calculated. Defaults to all vertices.
- directed
- Whether to consider directed paths in directed graphs, this argument is ignored for undirected graphs.
- unconnected
- What to do if the graph is unconnected (not strongly connected if directed paths are considered). If TRUE only the lengths of the existing paths are considered and averaged; if FALSE the length of the missing paths are counted having length
- verbose
- Logical scalar, whether to draw a progress meter while the calculation is running.

##### Details

The shortest paths (also called geodesics) are calculated by
using breath-first search in the graph. If no edge weights were
specified, then a breadth-first search is used to calculate the
shortest paths. If edge weigths are given and all of them are
non-zero, then Dijkstra's algorithm is used. Otherwise the
Bellman-Ford algorithm is used for `shortest.paths`

.

Please do NOT call `get.shortest.paths`

and
`get.all.shortest.paths`

with negative edge weights, it will not
work, these functions do not use the Belmann-Ford algotithm.

Note that `shortest.paths`

is able to calculate the path length
from or to many vertices at the same time, but
`get.shortest.paths`

works from one source only. This might
change in the future.

Also note that `get.shortest.paths`

gives only one shortest path,
however, more than one might exist between two vertices.

`get.all.shortest.paths`

calculates all shortest paths from a
vertex to other vertices given in the `to`

argument.

`path.length.hist`

calculates a histogram, by calculating the
shortest path length between each pair of vertices. For directed
graphs both directions are considered, so every pair of vertices
appears twice in the histogram.

##### Value

- For
`shortest.paths`

a numeric matrix with`vcount(graph)`

columns and`length(v)`

rows. The shortest path length from a vertex to itself is always zero. For unreachable vertices`Inf`

is included.For

`get.shortest.paths`

a list of length`vcount(graph)`

. List element`i`

contains the vertex ids on the path from vertex`from`

to vertex`i`

(or the other way for directed graphs depending on the`mode`

argument). The vector also contains`from`

and`i`

as the first and last elements. If`from`

is the same as`i`

then it is only included once. If there is no path between two vertices then a numeric vector of length zero is returned as the list element.For

`get.all.shortest.paths`

a list is returned, each list element contains a shortest path from`from`

to a vertex in`to`

. The shortest paths to the same vertex are collected into consecutive elements of the list. For`average.path.length`

a single number is returned.`path.length.hist`

returns a named list with two entries:`res`

is a numeric vector, the histogram of distances,`unconnected`

is a numeric scalar, the number of pairs for which the first vertex is not reachable from the second. The sum of the two entries is always $n(n-1)$ for directed graphs and $n(n-1)/2$ for undirected graphs.

##### concept

- Shortest path
- Geodesic

##### References

West, D.B. (1996). *Introduction to Graph Theory.* Upper
Saddle River, N.J.: Prentice Hall.

##### Examples

```
g <- graph.ring(10)
shortest.paths(g)
get.shortest.paths(g, 5)
get.all.shortest.paths(g, 0, 5:7)
average.path.length(g)
## Weighted shortest paths
el <- matrix(nc=3, byrow=TRUE,
c(0,1,0, 0,2,2, 0,3,1, 1,2,0, 1,4,5, 1,5,2, 2,1,1, 2,3,1,
2,6,1, 3,2,0, 3,6,2, 4,5,2, 4,7,8, 5,2,2, 5,6,1, 5,8,1,
5,9,3, 7,5,1, 7,8,1, 8,9,4) )
g2 <- add.edges(graph.empty(10), t(el[,1:2]), weight=el[,3])
shortest.paths(g2, mode="out")
```

*Documentation reproduced from package igraph, version 0.5.5-3, License: GPL (>= 2)*