graphallshortestpaths
(Removed) Find all shortest paths in graph
graphallshortestpaths
has been removed. Use distances
instead.
Syntax
[
dist
] =
graphallshortestpaths(G
)
[dist
] =
graphallshortestpaths(G
, ...'Directed', DirectedValue
,
...)
[dist
] = graphallshortestpaths(G
,
...'Weights', WeightsValue
, ...)
Arguments
G
| N-by-N adjacency matrix that represents a graph. Nonzero entries
in matrix G represent the weights of the
edges. |
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 matrix being ignored.
Default is true . |
WeightsValue | Column vector that specifies custom weights for the edges in
matrix G . It must have one entry for
every nonzero value (edge) in matrix G .
The order of the custom weights in the vector must match the order
of the nonzero values in matrix G when it
is traversed column-wise. This property lets you use zero-valued
weights. By default, graphallshortestpaths gets
weight information from the nonzero entries in matrix
G . |
Description
Tip
For introductory information on graph theory functions, see Graph Theory Functions.
[
finds the shortest paths between every pair of nodes in the graph represented by matrix
dist
] =
graphallshortestpaths(G
)G
, using Johnson's algorithm. Input
G
is an N-by-N adjacency matrix that represents a graph.
Nonzero entries in matrix G
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.
[...] = graphallshortestpaths (
calls
G
,
'PropertyName
',
PropertyValue
, ...)graphallshortestpaths
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
] =
graphallshortestpaths(G
, ...'Directed', DirectedValue
,
...)DirectedValue
to false
for an
undirected graph. This results in the upper triangle of the matrix being ignored.
Default is true
.
[
lets you specify custom weights for the edges. dist
] = graphallshortestpaths(G
,
...'Weights', WeightsValue
, ...)WeightsValue
is a column vector having one entry for every nonzero value (edge) in matrix
G
. The order of the custom weights in the vector must
match the order of the nonzero values in matrix G
when it is
traversed column-wise. This property lets you use zero-valued weights. By default,
graphallshortestpaths
gets weight information from the nonzero
entries in matrix G
.
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).