Shortest (directed or undirected) paths between vertices
distances calculates the length of all the shortest paths from
or to the vertices in the network.
shortest_paths calculates one
shortest path (the path itself, and not just its length) from or to the
distance_table(graph, directed = TRUE)
mean_distance(graph, directed = TRUE, unconnected = TRUE)
distances(graph, v = V(graph), to = V(graph), mode = c("all", "out", "in"), weights = NULL, algorithm = c("automatic", "unweighted", "dijkstra", "bellman-ford", "johnson"))
shortest_paths(graph, from, to = V(graph), mode = c("out", "all", "in"), weights = NULL, output = c("vpath", "epath", "both"), predecessors = FALSE, inbound.edges = FALSE)
all_shortest_paths(graph, from, to = V(graph), mode = c("out", "all", "in"), weights = NULL)
- The graph to work on.
- Whether to consider directed paths in directed graphs, this argument is ignored for undirected graphs.
- 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
- Numeric vector, the vertices from which the shortest paths will be calculated.
- Numeric vector, the vertices to which the shortest paths will be
calculated. By default it includes all vertices. Note that for
distancesevery vertex must be included here at most once. (This is not required for
- Character constant, gives whether the shortest paths to or from
the given vertices should be calculated for directed graphs. If
outthen the shortest paths from the vertex, if
inthen to it will be considered. I
- Possibly a numeric vector giving edge weights. If this is
NULLand the graph has a
weightedge attribute, then the attribute is used. If this is
NAthen no weights are used (even if the graph has a
- 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 algorithm is use
- 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.
- Character scalar, defines how to report the shortest paths.
vpathmeans that the vertices along the paths are reported, this form was used prior to igraph version 0.6. epathmeans that the edges along the paths are report
- Logical scalar, whether to return the predecessor vertex
for each vertex. The predecessor of vertex
iin the tree is the vertex from which vertex
iwas reached. The predecessor of the start vertex (in the
- Logical scalar, whether to return the inbound edge for
each vertex. The inbound edge of vertex
iin the tree is the edge via which vertex
iwas reached. The start vertex and vertices that were not reached during the search will h
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.
distances calculates the lengths of pairwise shortest paths from
a set of vertices (
from) to another set of vertices (
uses different algorithms, depending on the
argorithm argument and
weight edge attribute of the graph. The implemented algorithms
are breadth-first search (
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
algorithm argument. (This is also the default.)
shortest_paths calculates a single shortest path (i.e. the path
itself, not just its length) between the source vertex given in
to the target vertices given in
breadth-first search for unweighted graphs and Dijkstra's algorithm for
weighted graphs. The latter only works if the edge weights are non-negative.
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.
mean_distance 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.
distance_table 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
distancesa numeric matrix with
length(v)rows. The shortest path length from a vertex to itself is always zero. For unreachable vertices
shortest_pathsa named list with four entries is returned:
vpath This itself is a list, of length
length(to); list element
icontains the vertex ids on the path from vertex
to[i](or the other way for directed graphs depending on the
modeargument). The vector also contains
ias the first and last elements. If
fromis the same as
ithen 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 this output is not requested in the
outputargument, then it will be
epath This is a list similar to
vpath, but the vectors of the list contain the edge ids along the shortest paths, instead of the vertex ids. This entry is set to
NULLif it is not requested in the
predecessors Numeric vector, the predecessor of each vertex in the
NULLif it was not requested.
inbound_edges Numeric vector, the inbound edge for each vertex, or
NULL, if it was not requested.
all_shortest_pathsa list is returned, each list element contains a shortest path from
fromto a vertex in
to. The shortest paths to the same vertex are collected into consecutive elements of the list.
mean_distancea single number is returned.
distance_tablereturns a named list with two entries:
resis a numeric vector, the histogram of distances,
unconnectedis 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.
West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall.
g <- make_ring(10) distances(g) shortest_paths(g, 5) all_shortest_paths(g, 1, 6:8) mean_distance(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(make_empty_graph(10), t(el[,1:2]), weight=el[,3]) distances(g2, mode="out")