Main Content

graphshortestpath

(Removed) Solve shortest path problem in graph

graphshortestpath has been removed. Use shortestpath or shortestpathtree instead.

Description

[dist,path,pred] = graphshortestpath(G,S) determines the shortest paths from the source node S to all other nodes in the graph G. dist contains the distances from the source node to all other nodes. path contains the shortest paths to every node. pred contains the predecessor nodes of the shortest paths.

[___] = graphshortestpath(G,S,D) determines the shortest path from the source node S to the target node D and returns any of the output arguments from the previous syntax.

[___] = graphshortestpath(___,Name,Value) 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.

Input Arguments

collapse all

Adjacency matrix, specified as an N-by-N matrix that represents a graph. Nonzero entries in the matrix represent the weights of the edges.

Data Types: double | single | logical

Source node, specified as a numeric node index.

Example: 2

Data Types: double

Destination node, specified as a numeric node index.

Example: 5

Data Types: double

Name-Value Arguments

Specify optional pairs of arguments as Name1=Value1,...,NameN=ValueN, where Name is 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.

Example: [dist,path,pred] = graphshortestpath(G,1,5,'Method',Acyclic') assumes G to be a directed acyclic graph when finding the shortest path from node 1 to node 5.

Shortest path algorithm, specified as the comma-separated pair consisting of 'Method' and one of these options.

OptionDescription

'Dijkstra' (default)

This algorithm assumes that all edge weights are positive values in G. The time complexity is O(log(N)*E), where N and E are the number of nodes and the number of edges respectively.

'BFS'

This breadth-first search algorithm assumes that all weights are equal and that edges are nonzero entries in the adjacency matrix G. The time complexity is O(N+E).

'Bellman-Ford'

This algorithm assumes that all edge weights are nonzero entries in G. The time complexity is O(N*E).

'Acyclic'

This algorithm assumes that G is a directed acyclic graph and all edge weights are nonzero entries in G. The time complexity is O(N+E).

Example: 'Method','Acyclic'

Data Types: char | string

Directed or undirected graph flag, specified as a comma-separated pair consisting of 'Directed' and true or false. If false, the function ignores the upper triangle of the adjacency matrix G.

Example: 'Directed',false

Data Types: logical

Custom weights for edges in the matrix G, specified as a comma-separated pair consisting of '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 G.

  • 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 G.

Example: 'Weights',[1 2.3 1.3 0 4]

Data Types: double

Output Arguments

collapse all

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.

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.

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 path = [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 node.

pred(2) = 6; pred(6) = 4; pred(4) = 5; pred(5) = 1; pred(1) = 0;
The results indicate that the shortest path from node 1 to node 2 is 1->5->4->6->2.

References

[1] Dijkstra, E. W. "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik. Vol. 1, Number 1, 1959, pp. 269–271.

[2] Bellman, R. "On a Routing Problem." Quarterly of Applied Mathematics. Vol. 16, Number 1, pp. 87–90.

[3] 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 History

Introduced in R2006b

expand all

R2022b: Removed

graphshortestpath has been removed. Use shortestpath or shortestpathtree instead.