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"),
weights = NULL)
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 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. `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 `weight` attribute). `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. 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.

### 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)
## 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) )
shortest.paths(g2, mode="out")
```

[Package igraph version 0.5.1 Index]