Use this if you are using igraph from R
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
given vertex.
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", "bellmanford", "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 )
graph 
The graph to work on. 
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

v 
Numeric vector, the vertices from which the shortest paths will be calculated. 
to 
Numeric vector, the vertices to which the shortest paths will be
calculated. By default it includes all vertices. Note that for

mode 
Character constant, gives whether the shortest paths to or from
the given vertices should be calculated for directed graphs. If 
weights 
Possibly a numeric vector giving edge weights. If this is

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 breadthfirst search is used, otherwise if all weights are positive, then Dijkstra's algorithm is used. If there are negative weights and we do the calculation for more than 100 sources, then Johnson's algorithm is used. Otherwise the BellmanFord algorithm is used. You can override igraph's choice by explicitly giving this parameter. Note that the igraph C core might still override your choice in obvious cases, i.e. if there are no edge weights, then the unweighted algorithm will be used, regardless of this argument. 
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. 
output 
Character scalar, defines how to report the shortest paths. “vpath” means that the vertices along the paths are reported, this form was used prior to igraph version 0.6. “epath” means that the edges along the paths are reported. “both” means that both forms are returned, in a named list with components “vpath” and “epath”. 
predecessors 
Logical scalar, whether to return the predecessor vertex
for each vertex. The predecessor of vertex 
inbound.edges 
Logical scalar, whether to return the inbound edge for
each vertex. The inbound edge of vertex 
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 (to
). It
uses different algorithms, depending on the algorithm
argument and
the weight
edge attribute of the graph. The implemented algorithms
are breadthfirst search (‘unweighted
’), this only works for
unweighted graphs; the Dijkstra algorithm (‘dijkstra
’), this
works for graphs with nonnegative edge weights; the BellmanFord algorithm
(‘bellmanford
’), and Johnson's algorithm
(‘"johnson"
’). The latter two algorithms work with arbitrary
edge weights, but (naturally) only for graphs that don't have a negative
cycle.
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 ‘automatic
’ as the
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 from
,
to the target vertices given in to
. shortest_paths
uses
breadthfirst search for unweighted graphs and Dijkstra's algorithm for
weighted graphs. The latter only works if the edge weights are nonnegative.
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 breadthfirst search for unweighted
graphs and Dijkstra's algorithm for weighted ones. The latter only supports
nonnegative 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 breadthfirst 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
histogram.
For distances
a numeric matrix with length(to)
columns and length(v)
rows. The shortest path length from a vertex to
itself is always zero. For unreachable vertices Inf
is included.
For shortest_paths
a named list with four entries is returned:
vpath 
This itself is a list, of length 
epath 
This is a list similar to 
predecessors 
Numeric vector, the
predecessor of each vertex in the 
inbound_edges 
Numeric vector, the inbound edge
for each vertex, or 
For 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 mean_distance
a single number is returned.
distance_table
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(n1)
for directed graphs and n(n1)/2 for undirected graphs.
Gabor Csardi csardi.gabor@gmail.com
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")