MATLAB: How to get the nodes/vertices traversed from graphallshortestpaths function

graphallshortestpaths

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!

Best Answer

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 .
Related Question