# 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), to=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("out", "all",
"in"), weights = NULL, output=c("vpath", "epath", "both"))
get.all.shortest.paths(graph, from, to = V(graph), mode = c("out",
"all", "in"), weights=NULL)
average.path.length(graph, directed=TRUE, unconnected=TRUE)
path.length.hist (graph, directed = TRUE)
```

##### Arguments

- graph
- The graph to work on.
- v
- Numeric vector, the vertices from which the shortest paths will be calculated.
- to
- Numeric vector, the vertices to which the shortest paths
will be calculated. By default it includes all vertices. Note that
for
`shortest.paths`

every vertex must be included here at most once. (This is not required for`get.sh`

- 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.
- output
- Character scalar, defines how to report the shortest
paths.
vpath means that the vertices along the paths are reported, this form was used prior to igraph version 0.6.epath means that the edges along the path - 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

##### Details

The shortest path, or geodesic between two pair of vertices is a path
with the minimal number of vertices. The functions documented in this
manual page all calculate shortest paths between vertex pairs.
`shortest.paths`

calculates the lengths of pairwise shortest
paths from a set of vertices (`from`

) to another set of vertices
(`to`

). It uses different algorithms, depending on the
`argorithm`

argument and the `weight`

edge attribute of the
graph. The implemented algorithms are breadth-first search
(`unweighted`

`dijkstra`

`bellman-ford`

`"johnson"`

igraph can choose automatically between algorithms, and chooses the
most efficient one that is appropriate for the supplied weights (if
any). For automatic algorithm selection, supply
`automatic`

`algorithm`

argument. (This is
also the default.)

`get.shortest.paths`

calculates a single shortest path (i.e. the
path itself, not just its length) between the source vertex
given in `from`

, to the target vertices given in
`to`

. `get.shortest.paths`

uses breadth-first search for
unweighted graphs and Dijkstra's algorithm for weighted graphs. The
latter only works if the edge weights are non-negative.

`get.all.shortest.paths`

calculates *all* shortest paths
between pairs of vertices. More precisely, between the `from`

vertex to the vertices given in `to`

. It uses a breadth-first
search for unweighted graphs and Dijkstra's algorithm for weighted
ones. The latter only supports non-negative edge weights.

`average.path.length`

calculates the average path length in a
graph, by calculating the shortest paths between all pairs of vertices
(both ways for directed graphs). This function does not consider edge
weights currently and uses a breadth-first search.
`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`length(to)`

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`

the return value depends on the`output`

parameter. If this isvpath , then a list of length`vcount(graph)`

is returned. 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.If

`output`

isepath , then a similar list is returned, but the vectors in the list contain the edge ids along the shortest paths, instead of the vertex ids.If

`output`

isboth , then both lists are returned, in a named list with entries named asvpath andepath . 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, 1, 6:8)
average.path.length(g)
## Weighted shortest paths
el <- matrix(nc=3, byrow=TRUE,
c(1,2,0, 1,3,2, 1,4,1, 2,3,0, 2,5,5, 2,6,2, 3,2,1, 3,4,1,
3,7,1, 4,3,0, 4,7,2, 5,6,2, 5,8,8, 6,3,2, 6,7,1, 6,9,1,
6,10,3, 8,6,1, 8,9,1, 9,10,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.6.5-2, License: GPL (>= 2)*