# How does shortestpath function work?

5 views (last 30 days)
Riccardo Nebuloni on 7 Dec 2021
Hi everyone. i need a help.
i don't completely understand the "Shortest Path in Multigraph" example in "shortestpath" function (in particular, the edgepth). i don't understand the meaning of the indeces [1 7 9 10]: i thought they were the indeces of the couples of coordinates, but -if i were right- these couples shoud be 1-2/2,4/3,5/3,5 (that are not the right ones, couse in the "highlight" part and in the plot part everithing is ok.

Christine Tobler on 7 Dec 2021
Every edge has a number, which is the order in which they appear in the Edges table (try displaying g.Edges). The edgepath contains the number of each edge on the path:
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])
G =
graph with properties: Edges: [12×2 table] Nodes: [5×0 table]
G.Edges
ans = 12×2 table
EndNodes Weight ________ ______ 1 2 2 1 2 4 1 2 6 1 2 8 1 2 10 2 3 5 2 4 3 2 4 9 3 4 1 3 5 5 3 5 6 4 5 8
So the array [1 7 9 10] points to the first, 7th, 9th and 10th rows of the Edges table as the edges on the path (this is relevant for a multigraph because there can be several edges between the same two nodes).
If we index into the Edges table using edgepath, we get just a table of the edges that are on the path (see g.Edges(edgepath, :) in the example).
Christine Tobler on 7 Dec 2021
I see. The Edges table is always put into a standard format, as this makes it easier to compare graphs and the algorithms are much more efficient this way.
You can maintain the information about the original order of the edges by having the weights of the graph store this original order:
a=[1 1 1 1 1 2 2 3 3 3 4 4];
b= [2 2 2 2 2 3 4 4 5 5 5 2];
G = graph(a, b, 1:length(a));
G.Edges
ans = 12×2 table
EndNodes Weight ________ ______ 1 2 1 1 2 2 1 2 3 1 2 4 1 2 5 2 3 6 2 4 7 2 4 12 3 4 8 3 5 9 3 5 10 4 5 11
Here the weight of each edge is giving the order in which it appeared in the original inputs.

### Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

R2021b

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!