shortest.paths {igraph} R Documentation

## Shortest (directed or undirected) paths between vertices

### Description

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

### Usage

```shortest.paths(graph, v=V(graph), mode = c("all", "out", "in"))
get.shortest.paths(graph, from, to=V(graph), mode = c("all", "out", "in"))
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 considered. If `all`, the default, then the corresponding undirected graph will be used, ie. not directed paths are searched. This argument is ignored for undirected graphs. `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 `vcount(graph)`, one longer than the longest possible geodesic in the network. `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. 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.

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

### Author(s)

Gabor Csardi csardi@rmki.kfki.hu

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

[Package igraph version 0.5 Index]