shortestpath (biograph)
(To be removed) Solve shortest path problem in biograph object
shortestpath (biograph)
will be removed in a future release. Use the shortestpath
function of graph
or digraph
instead.
Syntax
[
dist
, path
, pred
] = shortestpath(BGObj
, S
)
[dist
, path
, pred
] = shortestpath(BGObj
, S
, T
)
[...] = shortestpath(..., 'Directed', DirectedValue
, ...)
[...] = shortestpath(..., 'Method', MethodValue
, ...)
[...] = shortestpath(..., 'Weights', WeightsValue
, ...)
Arguments
BGObj
 Biograph object created by biograph (object
constructor). 
S  Node in graph represented by an NbyN adjacency matrix extracted
from a biograph object, BGObj . 
T  Node in graph represented by an NbyN adjacency matrix extracted
from a biograph object, BGObj . 
DirectedValue  Property that indicates whether the graph represented by the NbyN
adjacency matrix extracted from a biograph object,
BGObj , 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 . 
MethodValue  Character vector or string that specifies the algorithm used to find
the shortest path. Choices are:

WeightsValue  Column vector that specifies custom weights for the edges in the
NbyN adjacency matrix extracted from a biograph object,
BGObj . It must have one entry for every
nonzero value (edge) in the NbyN adjacency matrix. The order of the
custom weights in the vector must match the order of the nonzero values
in the NbyN adjacency matrix when it is traversed columnwise. This
property lets you use zerovalued weights. By default,
shortestpaths gets weight information from the
nonzero entries in the NbyN adjacency matrix. 
Description
Tip
For introductory information on graph theory functions, see Graph Theory Functions.
[
determines the singlesource shortest paths from node dist
, path
, pred
] = shortestpath(BGObj
, S
)S
to
all other nodes in the graph represented by an NbyN adjacency matrix extracted from a
biograph object, BGObj
. Weights of the edges are all nonzero
entries in the NbyN adjacency matrix. dist
are the
N
distances from the source to every node (using
Inf
s for nonreachable nodes and 0
for the
source node). path
contains the winning paths to every node.
pred
contains the predecessor nodes of the winning paths.
[
determines the single sourcesingle destination shortest path from node
dist
, path
, pred
] = shortestpath(BGObj
, S
, T
)S
to node T
.
[...] = shortestpath(..., '
calls
PropertyName
',
PropertyValue
, ...)shortestpath
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:
[...] = shortestpath(..., 'Directed',
indicates whether the graph represented by the NbyN adjacency matrix extracted from a
biograph object, DirectedValue
, ...)BGObj
, is directed or undirected. Set
DirectedValue
to false
for an
undirected graph. This results in the upper triangle of the sparse matrix being ignored.
Default is true
.
[...] = shortestpath(..., 'Method',
lets you specify the algorithm used to find the shortest path. Choices are:MethodValue
, ...)
'BellmanFord'
— Assumes weights of the edges to be nonzero entries in the NbyN adjacency matrix. Time complexity isO(N*E)
, whereN
andE
are the number of nodes and edges respectively.'BFS'
— Breadthfirst search. Assumes all weights to be equal, and nonzero entries in the NbyN adjacency matrix to represent edges. Time complexity isO(N+E)
, whereN
andE
are the number of nodes and edges respectively.'Acyclic'
— Assumes the graph represented by the NbyN adjacency matrix extracted from a biograph object,BGObj
, to be a directed acyclic graph and that weights of the edges are nonzero entries in the NbyN adjacency matrix. Time complexity isO(N+E)
, whereN
andE
are the number of nodes and edges respectively.'Dijkstra'
— Default algorithm. Assumes weights of the edges to be positive values in the NbyN adjacency matrix. Time complexity isO(log(N)*E)
, whereN
andE
are the number of nodes and edges respectively.
[...] = shortestpath(..., 'Weights',
lets you specify custom weights for the edges. WeightsValue
, ...)WeightsValue
is a column vector having one entry for every nonzero value (edge) in the NbyN
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 NbyN adjacency matrix when it is traversed columnwise. This property lets you use
zerovalued weights. By default, shortestpath
gets weight information
from the nonzero entries in the NbyN adjacency matrix.
References
[1] Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271.
[2] Bellman, R. (1958). On a Routing Problem. Quarterly of Applied Mathematics 16(1), 87–90.
[3] Siek, J.G., Lee, LQ, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).
Version History
Introduced in R2006bSee Also
shortestpath
 graph
 digraph