allshortestpaths (biograph)
(Removed) Find all shortest paths in biograph object
allshortestpaths
has been removed. Use distances
instead.
Syntax
[
dist
] =
allshortestpaths(BGObj
)
[dist
] =
allshortestpaths(BGObj
, ...'Directed', DirectedValue
,
...)
[dist
] = allshortestpaths(BGObj
,
...'Weights', WeightsValue
, ...)
Arguments
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
adjacency 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. |
Description
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
is the distance of the
shortest path from source node 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 adjacency 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.
References
[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).