Solve shortest path problem in graph
[
dist
, path
, pred
] = graphshortestpath(G
, S
)
[dist
, path
, pred
] = graphshortestpath(G
, S
, T
)
[...] = graphshortestpath(..., 'Directed', DirectedValue
, ...)
[...] = graphshortestpath(..., 'Method', MethodValue
, ...)
[...] = graphshortestpath(..., 'Weights', WeightsValue
, ...)
G  NbyN sparse matrix that represents a graph. Nonzero entries
in matrix G represent the weights of the
edges. 
S  Node in G . 
T  Node in G . 
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 . 
MethodValue  Character vector that specifies the algorithm used to find
the shortest path. Choices are:

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
columnwise. This property lets you use zerovalued weights. By default, graphshortestpaths gets
weight information from the nonzero entries in matrix G . 
For introductory information on graph theory functions, see Graph Theory Functions.
[
determines the
singlesource shortest paths from node dist
, path
, pred
] = graphshortestpath(G
, S
)S
to
all other nodes in the graph represented by matrix G
.
Input G
is an NbyN sparse matrix that
represents a graph. Nonzero entries in matrix G
represent
the weights of the edges. 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
] = graphshortestpath(G
, S
, T
)S
to
node T
.
[...] = graphshortestpath(..., '
calls PropertyName
', PropertyValue
, ...)graphshortestpath
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:
[...] = graphshortestpath(..., 'Directed',
indicates whether the graph
is directed or undirected. Set DirectedValue
, ...)DirectedValue
to false
for
an undirected graph. This results in the upper triangle of the sparse
matrix being ignored. Default is true
.
[...] = graphshortestpath(..., '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 sparse matrix G
.
Time complexity is O(N*E)
, where N
and E
are
the number of nodes and edges respectively.
'BFS'
— Breadthfirst search.
Assumes all weights to be equal, and nonzero entries in sparse matrix G
to
represent edges. Time complexity is O(N+E)
, where N
and E
are
the number of nodes and edges respectively.
'Acyclic'
— Assumes G
to
be a directed acyclic graph and that weights of the edges are nonzero
entries in sparse matrix G
. Time complexity is O(N+E)
,
where N
and E
are the number
of nodes and edges respectively.
'Dijkstra'
— Default algorithm.
Assumes weights of the edges to be positive values in sparse matrix G
.
Time complexity is O(log(N)*E)
, where N
and E
are
the number of nodes and edges respectively.
[...] = graphshortestpath(..., 'Weights',
lets you specify custom weights
for the edges. 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 columnwise. This property lets you use zerovalued
weights. By default, graphshortestpath
gets weight
information from the nonzero entries in matrix G
.
Create and view a directed graph with 6 nodes and 11 edges.
W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21]; DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W) DG = (4,1) 0.4500 (6,2) 0.4100 (2,3) 0.5100 (5,3) 0.3200 (6,3) 0.2900 (3,4) 0.1500 (5,4) 0.3600 (1,5) 0.2100 (2,5) 0.3200 (1,6) 0.9900 (4,6) 0.3800 h = view(biograph(DG,[],'ShowWeights','on')) Biograph object with 6 nodes and 11 edges.
Find the shortest path in the graph from node 1 to node 6.
[dist,path,pred] = graphshortestpath(DG,1,6) dist = 0.9500 path = 1 5 4 6 pred = 0 6 5 5 1 4
Mark the nodes and edges of the shortest path by coloring them red and increasing the line width.
set(h.Nodes(path),'Color',[1 0.4 0.4]) edges = getedgesbynodeid(h,get(h.Nodes(path),'ID')); set(edges,'LineColor',[1 0 0]) set(edges,'LineWidth',1.5)
Create and view an undirected graph with 6 nodes and 11 edges.
UG = tril(DG + DG') UG = (4,1) 0.4500 (5,1) 0.2100 (6,1) 0.9900 (3,2) 0.5100 (5,2) 0.3200 (6,2) 0.4100 (4,3) 0.1500 (5,3) 0.3200 (6,3) 0.2900 (5,4) 0.3600 (6,4) 0.3800 h = view(biograph(UG,[],'ShowArrows','off','ShowWeights','on')) Biograph object with 6 nodes and 11 edges.
Find the shortest path in the graph from node 1 to node 6.
[dist,path,pred] = graphshortestpath(UG,1,6,'directed',false)
dist =
0.8200
path =
1 5 3 6
pred =
0 5 5 1 1 3
Mark the nodes and edges of the shortest path by coloring them red and increasing the line width.
set(h.Nodes(path),'Color',[1 0.4 0.4]) fowEdges = getedgesbynodeid(h,get(h.Nodes(path),'ID')); revEdges = getedgesbynodeid(h,get(h.Nodes(fliplr(path)),'ID')); edges = [fowEdges;revEdges]; set(edges,'LineColor',[1 0 0]) set(edges,'LineWidth',1.5)
[1] Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269271.
[2] Bellman, R. (1958). On a Routing Problem. Quarterly of Applied Mathematics 16(1), 8790.
[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).
graphallshortestpaths
 graphconncomp
 graphisdag
 graphisomorphism
 graphisspantree
 graphmaxflow
 graphminspantree
 graphpred2path
 graphtopoorder
 graphtraverse
 shortestpath