How does shortestpath function work?

2021 12 7
1 个回答
回答已采纳
更新时间：2021 12 7
8 次查看（30 天）

0 个投票

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.
Thx for your help

请先登录，再回答此问题。

 采纳的回答

Christine Tobler
Christine Tobler 2021-12-7
Ran in:

1 个投票

Ran in:
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).

4 个评论
显示 2更早的评论 隐藏 2更早的评论

Riccardo Nebuloni
Riccardo Nebuloni 2021-12-7
thank you @Christine Tobler, now i get it.
as you can see the indeces of the input "lines" are different to the ones found in the table. is there a way to keep the same order of the input data?
Christine Tobler
Christine Tobler 2021-12-7
Do you mean the values in the Weight column of the Edges table? Those are just inserted as being the "length" of each edge, they're not supposed to map to the edge indices.
Riccardo Nebuloni
Riccardo Nebuloni 2021-12-7
no, i mean the first two vectors inside []:
lets call them a=[1 1 1 1 1 2 2 3 3 3 4 4] and b= [2 2 2 2 2 3 4 4 5 5 5 2].
the branch matrix will be C= [a' b']. i will obtain line indeces that link the starting and final points of a branch eg:
  1. 1-2
  2. 1-2
  3. 1-2
  4. 1-2
  5. 1-2
  6. 2-3
  7. 2-4
  8. 3-4
  9. 3-5
  10. 3-5
  11. 4-5
  12. 4-2
this order is not the same of the first two columns of the table. my question is: is there a way to keep the input order of the nodes?
Christine Tobler
Christine Tobler 2021-12-7
Ran in:
Ran in:
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.

请先登录，再进行评论。

更多回答（0 个）

类别

在 帮助中心 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

产品

版本

R2021b

标签

Community Treasure Hunt

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

Start Hunting!

Translated by