%% 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(x_i ,y_i \right) as:
% d=\sqrt{{\left|\Delta x\right|}^2 +{\left|\Delta y\right|}^2 }=\sqrt{{\left|x_s -x_t \right|}^2 +{\left|y_s -y_t \right|}^2 }\ldotp
% To calculate \Delta x and \Delta 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 x=x_s -x_t and \Delta y=y_s -y_t. The hypot function computes the squareroot of the sum of squares, so specify \Delta x and \Delta 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)

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

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

%
% Copyright 2020 The MathWorks, Inc.