(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
numeric node index
Source node, specified as a numeric node index.
D — Destination node
numeric node index
Destination node, specified as a numeric node index.
Specify optional pairs of arguments as
the argument name and
Value is the corresponding value.
Name-value arguments must appear after other arguments, but the order of the
pairs does not matter.
Before R2021a, use commas to separate each name and value, and enclose
Name in quotes.
[dist,path,pred] = graphshortestpath(G,1,5,'Method',Acyclic')
G to be a directed acyclic graph when finding the shortest path
1 to node
Method — Shortest path algorithm
'Dijkstra' (default) |
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
true (default) |
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
Gwhen 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
numeric scalar | numeric vector
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
vector | cell array
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;
 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.
Version HistoryIntroduced in R2006b
graphshortestpath issues a warning that it will be removed in a future
R2021b: To be removed
graphshortestpath runs without warning, but it will be removed in a future
R2021b: Full matrices are supported
The function now supports full matrices in addition to sparse matrices.
R2021b: Edges with infinite weight are now included in the shortest path
The function uses edges with infinite weight and include them in the shortest path if no paths with finite length exist.