Find all shortest paths in biograph object
[dist] =
allshortestpaths(BGObj)
[dist] =
allshortestpaths(BGObj, ...'Directed', DirectedValue,
...)
[dist] = allshortestpaths(BGObj,
...'Weights', WeightsValue, ...)
BGObj | Biograph object created by biograph (object constructor). |
DirectedValue | Property that indicates whether the graph
is directed or undirected. Enter false for an undirected
graph. This results in the upper triangle of the sparse matrix being
ignored. Default is true. |
WeightsValue | Column vector that specifies custom
weights for the edges in the N-by-N adjacency matrix extracted from
a biograph object, BGObj. It must have
one entry for every nonzero value (edge) in the matrix. The order
of the custom weights in the vector must match the order of the nonzero
values in the matrix when it is traversed column-wise. This property
lets you use zero-valued weights. By default, allshortestpaths gets
weight information from the nonzero entries in the matrix. |
Tip
For introductory information on graph theory functions, see Graph Theory Functions.
[ finds
the shortest paths between every pair of nodes in a graph represented
by an N-by-N adjacency matrix extracted from a biograph object, dist] =
allshortestpaths(BGObj)BGObj,
using Johnson's algorithm. Nonzero entries in the matrix represent
the weights of the edges.
Output dist is an N-by-N matrix
where dist(S,T)S to
target node T. Elements in the diagonal of this
matrix are always 0, indicating the source node
and target node are the same. A 0 not in the diagonal
indicates that the distance between the source node and target node
is 0. An Inf indicates there
is no path between the source node and the target node.
Johnson's algorithm has a time complexity of O(N*log(N)+N*E),
where N and E are the number
of nodes and edges respectively.
[...] = allshortestpaths ( calls BGObj,
'PropertyName', PropertyValue,
...)allshortestpaths with optional
properties that use property name/property value pairs. You can specify
one or more properties in any order. Each PropertyName must
be enclosed in single quotes and is case insensitive. These property
name/property value pairs are as follows:
[ indicates whether the graph is directed
or undirected. Set dist] =
allshortestpaths(BGObj, ...'Directed', DirectedValue,
...)DirectedValue to false for
an undirected graph. This results in the upper triangle of the sparse
matrix being ignored. Default is true.
[ lets
you specify custom weights for the edges. dist] = allshortestpaths(BGObj,
...'Weights', WeightsValue, ...)WeightsValue is
a column vector having one entry for every nonzero value (edge) in
the N-by-N adjacency matrix extracted from a biograph object, BGObj.
The order of the custom weights in the vector must match the order
of the nonzero values in the N-by-N adjacency matrix when it is traversed
column-wise. This property lets you use zero-valued weights. By default, allshortestpaths gets
weight information from the nonzero entries in the N-by-N adjacency
matrix.
[1] Johnson, D.B. (1977). Efficient algorithms for shortest paths in sparse networks. Journal of the ACM 24(1), 1-13.
[2] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).
biograph | conncomp | graphallshortestpaths | isdag | isomorphism | isspantree | maxflow | minspantree | shortestpath | topoorder | traverse