graphshortestpath

Solve shortest path problem in graph

Syntax

[dist,path,pred] = graphshortestpath(G,S)

[___] = graphshortestpath(G,S,D)

[___] = graphshortestpath(___,Name,Value)

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.

Examples

Find Shortest Paths in Directed Graph

Create 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

Display the graph.

h = view(biograph(DG,[],'ShowWeights','on'))

Biograph object with 6 nodes and 11 edges.

Find the shortest path from node 1 to node 6.

[dist,path,pred] = graphshortestpath(DG,1,6)

dist = 0.9500

path = 1×4

     1     5     4     6

pred = 1×6

     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)

pred contains predecessor nodes of the shortest paths from node 1, the source node, to all other nodes, not only the specified destination node. You can use pred to query the shortest paths from the source node to any other node in the graph.

For instance, to figure out the shortest path from node 1 to node 4 using the information in pred, query pred with the destination node as the first query. Then use the returned answer to get the next node. Repeat this procedure until you get the query answer as 0, which indicates the source node.

next = pred(4)

next = 5

next = pred(next)

next = 1

next = pred(next)

next = 0

The results indicate that the shortest path from node 1 to node 4 is 1->5->4.

Find Shortest Paths in Undirected Graph

Create an undirected 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);
% tril returns the lower triangular part of the matrix.
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

View the graph.

h = view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))

Biograph object with 6 nodes and 11 edges.

Find the shortest path from node 1 to node 6. Set 'Directed' to false to specify that the graph is not a directed graph.

[dist,path,pred] = graphshortestpath(UG,1,6,'Directed',false)

dist = 0.8200

path = 1×4

     1     5     3     6

pred = 1×6

     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)

Input Arguments

G — Adjacency matrix

matrix

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

Data Types: double

S — Source node

numeric node index

Source node, specified as a numeric node index.

Example: 2

Data Types: double

D — Destination node

numeric node index

Destination node, specified as a numeric node index.

Example: 5

Data Types: double

Name-Value Pair Arguments

Specify optional comma-separated pairs of Name,Value arguments. Name is 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 Name1,Value1,...,NameN,ValueN.

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.

'Method' — Shortest path algorithm

'Dijkstra' (default) | 'Bellman-Ford' | 'BFS' | 'Acyclic'

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

Option	Description
'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 sparse 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' — Directed or undirected graph flag

true (default) | false

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 sparse matrix G.

Example: 'Directed',false

Data Types: logical

'Weights' — Custom weights for edges in G

column vector

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

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

vector

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.