Dijkstra related problem / partial distances and nodes

Question

Nuno Palma 2016-12-8

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/316038-dijkstra-related-problem-partial-distances-and-nodes

回答： Image Analyst 2016-12-8

So, I'm building a program that takes an adjacency matrix and the goal is to calculate the shortest paths between the nodes.

Let's say I have the following matrix:

7 9 0 0 14
0 10 15 0 0
10 0 11 0 2
15 11 0 6 0
0 0 6 0 9
0 2 0 9 0

I used a basic Dijkstra function to obtain a vector containing the total distance and another one with the previous nods. So, in this case if I wanted to start from node 1. I'd obtain a vector dist = [ 0 7 9 20 20 11 ] and a vector previous = [ 0 1 1 3 6 3 ]

Now, I'm trying to find a way to obtain the nodes I'd have to take in the middle of the process, as well as the partial distances between them. The final result should be something like this:

(7) 2 | Total distance = 7
(9) 3 | Total distance = 9
(9) 3 (11) 4 | Total distance = 20
(9) 3 (2) 6 (9) 5 | Total distance = 20

I've tried different approaches to get a vector with the partial distances and another with the in-between nodes, but they all failed when there were more than 1 node separating the starting point and the last node. Any ideas how I can get there?