How can I get the nodes/vertices traversed from graphallshortestpaths function?

5 次查看（过去 30 天）
TLY
TLY 2016-1-19
评论： TLY 2016-1-22
I have a graph with undirected, weighted edges and have used the graphallshortestpaths function to solve the all-pairs shortest-path problem to determine the shortest distances between each pair of nodes. I would like to be able to find out the nodes that are being traversed for each path. Is this possible?
For example, given the following graph with 10 nodes and 33 edges:
nodeOrig nodeDest arcLength
1 2 3.16
1 3 7.07
1 4 3.61
1 5 2.00
1 6 8.49
1 7 8.25
2 3 4.47
2 4 3.00
2 7 5.10
2 8 3.16
2 9 5.00
2 10 11.00
3 4 7.28
3 5 8.60
3 6 11.05
3 9 9.22
3 10 15.13
4 5 3.00
4 6 5.00
4 7 6.40
4 8 6.08
4 10 8.00
5 6 7.21
5 7 8.94
5 9 3.61
6 7 8.25
6 8 10.77
6 9 3.61
6 10 5.00
7 8 6.32
7 10 13.00
8 9 8.06
9 10 6.00
and the following graphallshortestpaths solution:
0.00 3.16 7.07 3.61 2.00 8.49 8.25 6.32 5.61 11.61
3.16 0.00 4.47 3.00 5.16 8.00 5.10 3.16 5.00 11.00
7.07 4.47 0.00 7.28 8.60 11.05 9.57 7.63 9.22 15.13
3.61 3.00 7.28 0.00 3.00 5.00 6.40 6.08 6.61 8.00
2.00 5.16 8.60 3.00 0.00 7.21 8.94 8.32 3.61 9.61
8.49 8.00 11.05 5.00 7.21 0.00 8.25 10.77 3.61 5.00
8.25 5.10 9.57 6.40 8.94 8.25 0.00 6.32 10.10 13.00
6.32 3.16 7.63 6.08 8.32 10.77 6.32 0.00 8.06 14.06
5.61 5.00 9.22 6.61 3.61 3.61 10.10 8.06 0.00 6.00
11.61 11.00 15.13 8.00 9.61 5.00 13.00 14.06 6.00 0.00
is there a way to determine that the shortest path from node 1 to node 10 is 1-5-9-10 (for a total distance of 11.61)?
Thanks for your help!

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

采纳的回答

Pavithra Ashok Kumar
I understand that you want to get the shortest path to be traversed between two nodes. However, as the doc suggests, "graphallshortestpaths" would return only the distance matrix. However, you can use the "graphshortestpath" function to find the distance and shortest path. This function allows you to use different methods to calculate the path. Assuming you do not have any negative edges, it would not be much additional complexity to use the function between every pair of vertices to mimic "graphallshortestpaths". For more details, refer here .

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by