Dijkstra related problem / partial distances and nodes

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:

0 7 9 0 0 14

7 0 10 15 0 0

9 10 0 11 0 2

0 15 11 0 6 0

0 0 0 6 0 9

14 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:

1 (7) 2 | Total distance = 7

1 (9) 3 | Total distance = 9

1 (9) 3 (11) 4 | Total distance = 20

1 (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?

Answer 1

[Image Analyst]

You might want to read Steve Eddins's 5 part blog on the topic: http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/