shortestpath

Shortest path between two single nodes

Syntax

P = shortestpath(G,s,t)

P = shortestpath(G,s,t,'Method',algorithm)

[P,d] = shortestpath(___)

[P,d,edgepath] = shortestpath(___)

Description

P = shortestpath(G,s,t) computes the shortest path starting at source node s and ending at target node t. If the graph is weighted (that is, G.Edges contains a variable Weight), then those weights are used as the distances along the edges in the graph. Otherwise, all edge distances are taken to be 1.

P = shortestpath(G,s,t,'Method',algorithm) optionally specifies the algorithm to use in computing the shortest path. For example, if G is a weighted graph, then shortestpath(G,s,t,'Method','unweighted') ignores the edge weights in G and instead treats all edge weights as 1.

[P,d] = shortestpath(___) additionally returns the length of the shortest path, d, using any of the input arguments in previous syntaxes.

[P,d,edgepath] = shortestpath(___) additionally returns the edge indices edgepath of all edges on the shortest path from s to t.

Examples

Shortest Path Between Specified Nodes

Create and plot a directed graph.

s = [1 1 2 3 3 4 4 6 6 7 8 7 5];
t = [2 3 4 4 5 5 6 1 8 1 3 2 8];
G = digraph(s,t);
plot(G)

Calculate the shortest path between nodes 7 and 8.

P = shortestpath(G,7,8)

P = 1×5

     7     1     3     5     8

Shortest Path in Weighted Graph

Create and plot a graph with weighted edges.

s = [1 1 1 2 2 6 6 7 7 3 3 9 9 4 4 11 11 8];
t = [2 3 4 5 6 7 8 5 8 9 10 5 10 11 12 10 12 12];
weights = [10 10 10 10 10 1 1 1 1 1 1 1 1 1 1 1 1 1];
G = graph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

Find the shortest path between nodes 3 and 8, and specify two outputs to also return the length of the path.

[P,d] = shortestpath(G,3,8)

P = 1×5

     3     9     5     7     8

d = 4

Since the edges in the center of the graph have large weights, the shortest path between nodes 3 and 8 goes around the boundary of the graph where the edge weights are smallest. This path has a total length of 4.

Shortest Path Ignoring Edge Weights

Create and plot a graph with weighted edges, using custom node coordinates.

s = [1 1 1 1 1 2 2 7 7 9 3 3 1 4 10 8 4 5 6 8];
t = [2 3 4 5 7 6 7 5 9 6 6 10 10 10 11 11 8 8 11 9];
weights = [1 1 1 1 3 3 2 4 1 6 2 8 8 9 3 2 10 12 15 16];
G = graph(s,t,weights);

x = [0 0.5 -0.5 -0.5 0.5 0 1.5 0 2 -1.5 -2];
y = [0 0.5 0.5 -0.5 -0.5 2 0 -2 0 0 0];
p = plot(G,'XData',x,'YData',y,'EdgeLabel',G.Edges.Weight);

Find the shortest path between nodes 6 and 8 based on the graph edge weights. Highlight this path in green.

[path1,d] = shortestpath(G,6,8)

path1 = 1×5

     6     3     1     4     8

d = 14

highlight(p,path1,'EdgeColor','g')

Specify Method as unweighted to ignore the edge weights, instead treating all edges as if they had a weight of 1. This method produces a different path between the nodes, one that previously had too large of a path length to be the shortest path. Highlight this path in red.

[path2,d] = shortestpath(G,6,8,'Method','unweighted')

path2 = 1×3

     6     9     8

d = 2

highlight(p,path2,'EdgeColor','r')

Shortest Path in Multigraph

Plot the shortest path between two nodes in a multigraph and highlight the specific edges that are traversed.

Create a weighted multigraph with five nodes. Several pairs of nodes have more than one edge between them. Plot the graph for reference.

G = graph([1 1 1 1 1 2 2 3 3 3 4 4],[2 2 2 2 2 3 4 4 5 5 5 2],[2 4 6 8 10 5 3 1 5 6 8 9]);
p = plot(G,'EdgeLabel',G.Edges.Weight);

Find the shortest path between node 1 and node 5. Since several of the node pairs have more than one edge between them, specify three outputs to shortestpath to return the specific edges that the shortest path traverses.

[P,d,edgepath] = shortestpath(G,1,5)

P = 1×5

     1     2     4     3     5

d = 11

edgepath = 1×4

     1     7     9    10

The results indicate that the shortest path has a total length of 11 and follows the edges given by G.Edges(edgepath,:).

G.Edges(edgepath,:)

ans=4×2 table
    EndNodes    Weight
    ________    ______

     1    2       2   
     2    4       3   
     3    4       1   
     3    5       5   

Highlight this edge path by using the highlight function with the 'Edges' name-value pair to specify the indices of the edges traversed.

highlight(p,'Edges',edgepath)

Shortest Path from Node Coordinates

Find the shortest path between nodes in a graph using the distance between the nodes as the edge weights.

Create a graph with 10 nodes.

s = [1 1 2 2 3 4 4 4 5 5 6 6 7 8 9];
t = [2 4 3 5 6 5 7 9 6 7 7 8 9 10 10];
G = graph(s,t);

Create x- and y-coordinates for the graph nodes. Then plot the graph using the node coordinates by specifying the 'XData' and 'YData' name-value pairs.

x = [1 2 3 2 2.5 4 3 5 3 5];
y = [1 3 4 -1 2 3.5 1 3 0 1.5];
plot(G,'XData',x,'YData',y)

Add edge weights to the graph by computing the Euclidean distances between the graph nodes. The distance is calculated from the node coordinates $\left({\mathit{x}}_{\mathit{i}},{\mathit{y}}_{\mathit{i}}\right)$ as:

$$\mathit{d}=\sqrt{{\left|\Delta \mathit{x}\right|}^2+{\left|\Delta \mathit{y}\right|}^2}=\sqrt{{\left|{\mathit{x}}_{\mathit{s}}-{\mathit{x}}_{\mathit{t}}\right|}^2+{\left|{\mathit{y}}_{\mathit{s}}-{\mathit{y}}_{\mathit{t}}\right|}^2}.$$

To calculate $\Delta \mathit{x}$ and $\Delta \mathit{y}$, first use findedges to obtain vectors sn and tn describing the source and target nodes of each edge in the graph. Then use sn and tn to index into the x- and y-coordinate vectors and calculate $\Delta \mathit{x}={\mathit{x}}_{\mathit{s}}-{\mathit{x}}_{\mathit{t}}$ and $\Delta \mathit{y}={\mathit{y}}_{\mathit{s}}-{\mathit{y}}_{\mathit{t}}$. The hypot function computes the squareroot of the sum of squares, so specify $\Delta \mathit{x}$ and $\Delta \mathit{y}$ as the input arguments to calculate the length of each edge.

[sn,tn] = findedge(G);
dx = x(sn) - x(tn);
dy = y(sn) - y(tn);
D = hypot(dx,dy);

Add the distances to the graph as the edge weights and replot the graph with the edges labeled.

G.Edges.Weight = D';
p = plot(G,'XData',x,'YData',y,'EdgeLabel',G.Edges.Weight);

Calculate the shortest path between node 1 and node 10 and specify two outputs to also return the path length. For weighted graphs, shortestpath automatically uses the 'positive' method which considers the edge weights.

[path,len] = shortestpath(G,1,10)

path = 1×4

     1     4     9    10

len = 6.1503

Use the highlight function to display the path in the plot.

highlight(p,path,'EdgeColor','r','LineWidth',2)

Input Arguments

G — Input graph

graph object | digraph object

Input graph, specified as either a graph or digraph object. Use graph to create an undirected graph or digraph to create a directed graph.

Example: G = graph(1,2)

Example: G = digraph([1 2],[2 3])

s,t — Source and target node IDs (as separate arguments)

node indices | node names

Source and target node IDs, specified as separate arguments of node indices or node names.

Value	Example
Scalar node index	1
Character vector node name	'A'
String scalar node name	"A"

Example: shortestpath(G,2,5) computes the shortest path between node 2 and node 5.

Example: shortestpath(G,'node1','node2') computes the shortest path between the named nodes node1 and node2.

algorithm — Shortest path algorithm

'auto' (default) | 'unweighted' | 'positive' | 'mixed' | 'acyclic'

Shortest path algorithm, specified as one of the options in the table.

Option	Description
'auto' (default)	The 'auto' option automatically selects the algorithm: 'unweighted' is used for graph and digraph inputs with no edge weights. 'positive' is used for all graph inputs that have edge weights, and requires the weights to be nonnegative. This option is also used for digraph inputs with nonnegative edge weights. 'mixed' is used for digraph inputs whose edge weights contain some negative values. The graph cannot have negative cycles.
'unweighted'	Breadth-First computation that treats all edge weights as 1.
'positive'	Dijkstra algorithm that requires all edge weights to be nonnegative.
'mixed' (only for digraph)	Bellman-Ford algorithm for directed graphs that requires the graph to have no negative cycles. While 'mixed' is slower than 'positive' for the same problem, 'mixed' is more versatile as it allows some edge weights to be negative.
'acyclic' (only for digraph)	Algorithm designed to improve performance for directed, acyclic graphs (DAGs) with weighted edges. Use isdag to confirm if a directed graph is acyclic.

Note

For most graphs, 'unweighted' is the fastest algorithm, followed by 'acyclic', 'positive', and 'mixed'.

Example: shortestpath(G,s,t,'Method','acyclic')

Output Arguments

P — Shortest path between nodes

node indices | node names

Shortest path between nodes, returned as a vector of node indices or an array of node names. P is empty, {}, if there is no path between the nodes.

• If s and t contain numeric node indices, then P is a numeric vector of node indices.

• If s and t contain node names, then P is a cell array or string array containing node names.

If there are multiple shortest paths between s and t, then P contains only one of the paths. The path that is returned can change depending on which algorithm Method specifies.

d — Shortest path distance

scalar

Shortest path distance, returned as a numeric scalar. d is the summation of the edge weights between consecutive nodes in P. If there is no path between the nodes, then d is Inf.

edgepath — Edges on shortest path

vector of edge indices

Edges on shortest path, returned as a vector of edge indices. For multigraphs, this output indicates which edge between two nodes is on the path. This output is compatible with the 'Edges' name-value pair of highlight, for example: highlight(p,'Edges',edgepath).

Tips

• The shortestpath, shortestpathtree, and distances functions do not support undirected graphs with negative edge weights, or more generally any graph containing a negative cycle, for these reasons:

  • A negative cycle is a path that leads from a node back to itself, with the sum of the edge weights on the path being negative. If a negative cycle is on a path between two nodes, then no shortest path exists between the nodes, since a shorter path can always be found by traversing the negative cycle.

  • A single negative edge weight in an undirected graph creates a negative cycle.