graphshortestpath - Solve shortest path problem in graph

Syntax

Arguments

G	N-by-N 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	String that specifies the algorithm used to find the shortest path. Choices are: 'Bellman-Ford' — 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' — Breadth-first 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.
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 column-wise. This property lets you use zero-valued weights. By default, graphshortestpaths gets weight information from the nonzero entries in matrix G.

Description

Tip   For introductory information on graph theory functions, see Graph Theory Functions in the Bioinformatics Toolbox User's Guide.

[dist, path, pred] = graphshortestpath(G, S) determines the single-source shortest paths from node S to all other nodes in the graph represented by matrix G. Input G is an N-by-N 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 Infs 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.

[dist, path, pred] = graphshortestpath(G, S, T) determines the single source-single destination shortest path from node S to node T.

[...] = graphshortestpath(..., 'PropertyName', PropertyValue, ...) calls 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', DirectedValue, ...) indicates whether the graph is directed or undirected. Set DirectedValue to false for an undirected graph. This results in the upper triangle of the sparse matrix being ignored. Default is true.

[...] = graphshortestpath(..., 'Method', MethodValue, ...) lets you specify the algorithm used to find the shortest path. Choices are:

• 'Bellman-Ford' — 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' — Breadth-first 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', WeightsValue, ...) lets you specify custom weights for the edges. 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 column-wise. This property lets you use zero-valued weights. By default, graphshortestpath gets weight information from the nonzero entries in matrix G.

Examples

Finding the Shortest Path in a Directed Graph

1. 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.

   

2. 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

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])
   edges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));
   set(edges,'LineColor',[1 0 0])
   set(edges,'LineWidth',1.5)

   

Finding the Shortest Path in an Undirected Graph

1. 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.

   

2. 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

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)

   

References

[1] Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269-271.

[2] Bellman, R. (1958). On a Routing Problem. Quarterly of Applied Mathematics 16(1), 87-90.

[3] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).

See Also

graphallshortestpaths | graphconncomp | graphisdag | graphisomorphism | graphisspantree | graphmaxflow | graphminspantree | graphpred2path | graphtopoorder | graphtraverse | shortestpath

© 1984-2012- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS