igraph (version 0.5.3)

shortest.paths: 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, 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.

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

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.

References

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

Examples

Run this code
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")

Run the code above in your browser using DataCamp Workspace