# 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 = "all")
get.shortest.paths(graph, from, to=V(graph), mode = "all")
get.all.shortest.paths(graph, from, to = V(graph), mode = "all")
average.path.length(graph, directed=TRUE, unconnected=TRUE)
```

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

##### Details

The shortest paths (also called geodesics) are calculated by using breath-first search in the graph. Right now edge weights are not used, ie. every edge weight is one.

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 exists between two vertices.

`get.all.shortest.paths`

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

argument.

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

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

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

*Documentation reproduced from package igraph, version 0.4.4, License: GPL version 2 or later (June, 1991)*