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.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"))
out
then the shortest paths from the vertex, if
in
then to it will be cNULL
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
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.
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.
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