(To be removed) Solve shortest path problem in graph
the shortest paths from the source node
pred] = graphshortestpath(
S to all other nodes in
dist contains the distances from the
source node to all other nodes.
path contains the shortest paths to
pred contains the predecessor nodes of the shortest
[___] = graphshortestpath(___,
specifies additional options using one or more name-value pair arguments. Specify name-value
pair arguments after any of the input argument combinations in the previous syntaxes.
G— Adjacency matrix
Adjacency matrix, specified as an N-by-N matrix that represents a graph. Nonzero entries in the matrix represent the weights of the edges.
S— Source node
Source node, specified as a numeric node index.
D— Destination node
Destination node, specified as a numeric node index.
comma-separated pairs of
the argument name and
Value is the corresponding value.
Name must appear inside quotes. You can specify several name and value
pair arguments in any order as
[dist,path,pred] = graphshortestpath(G,1,5,'Method',Acyclic')assumes
Gto be a directed acyclic graph when finding the shortest path from node
Method— Shortest path algorithm
Shortest path algorithm, specified as the comma-separated pair consisting of
'Method' and one of these options.
This algorithm assumes that all edge weights are positive values
This breadth-first search algorithm assumes that all weights are
equal and that edges are nonzero entries in the adjacency matrix
This algorithm assumes that all edge weights are nonzero entries
This algorithm assumes that
Directed— Directed or undirected graph flag
Directed or undirected graph flag, specified as a comma-separated pair consisting
false, the function ignores the
upper triangle of the adjacency matrix
Weights— Custom weights for edges in
Custom weights for edges in the matrix G, specified as a comma-separated pair
'Weights' and a column vector. The vector must meet
the following conditions.
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
G when it is traversed columnwise.
You can specify zero-valued weights. By default, the function obtains the weight
information from the nonzero entries in
'Weights',[1 2.3 1.3 0 4]
dist— Distances from source node to all other nodes in graph
Distances from the source node to all other nodes in the graph, returned as a
numeric scalar or vector.
dist is returned as a scalar if you
specify a destination node as the third input argument.
The function returns
Inf for nonreachable nodes and
0 for the source node.
path— Shortest paths from source node to all other nodes
Shortest paths from the source node to all other nodes, returned as a vector or cell array. It is returned as a vector if you specify a destination node. Each number represents a node index in the graph.
pred— Predecessor nodes of shortest paths
Predecessor nodes of the shortest paths, returned as a vector.
You can use
pred to determine the shortest paths from the source
node to all other nodes. Suppose that you have a directed graph with 6 nodes.
The function finds that the shortest path from node 1 to node 6 is
[1 5 4 6] and
pred = [0 6 5 5 1 4]. Now you can determine
the shortest paths from node 1 to any other node within the graph by indexing into
pred. For example, to figure out the shortest path from node 1 to
node 2, you can query
pred with the destination node as the first
query, then use the returned answer to get the next node. Repeat this procedure until
the query answer is 0, which indicates the source
pred(2) = 6; pred(6) = 4; pred(4) = 5; pred(5) = 1; pred(1) = 0;
graphshortestpathwill be removed
Not recommended starting in R2021b
Behavior changed in R2021b
The function now supports full matrices in addition to sparse matrices.
Behavior changed in R2021b
The function uses edges with infinite weight and include them in the shortest path if no paths with finite length exist.
 Dijkstra, E. W. "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik. Vol. 1, Number 1, 1959, pp. 269–271.
 Bellman, R. "On a Routing Problem." Quarterly of Applied Mathematics. Vol. 16, Number 1, pp. 87–90.
 Siek, J. G., L. Q. Lee, and A. Lumsdaine. The Boost Graph Library: User Guide and Reference Manual. Upper Saddle River, NJ: Pearson Education, 2002.