1. ## Understanding Dijkstra

Hey,
I havnt done dijkstra for a while and im having trouble understanding the universities notes etc.

For a very simple graph, nodes 1, 2, 3
{1,2} = length 2
{1, 3} = length 3
{2, 3} = length 2

Now, naturally, i'd have though Dijkstra's spanning tree starting from node 3 would be {2, 3} + {1,3} = 5

However, via table:
Nodes:
1 2 3
---------------------------
3 | 3 2 0 | Lowest is 2 so i highlight this. And write node 2 in next row
2 | 2 2 | lowest is 2

However this gives a spanning tree of {1,2}, {2, 3} = 4.

And whilst this is lower, i'd have thought it'd be the other...

What am i doing wrong? I have a feeling it's the table and i should be adding something to the values and checking each node, rather then selecting the lowest and taking the row it is in.

2. In case this is still relevant... It has been some time since I studied the algorithm myself, and I don't know how to execute it via a table. However, first, it is not Dijkstra's, but Prim's algorithm that finds a minimal spanning tree. The goal of Dijkstra's algorithm is to mark each vertex with the shortest distance from the initial vertex. It is not clear to me how to recover a spanning tree from the order of visited vertices.

In Dijkstra's algorithm, if you start with vertex 3, you mark vertex 2 with distance 2 and vertex 1 with distance 3, and you mark 3 as visited. Then you go to vertex 2, as having the least label, and consider its neighbor 1, but 1's label is already smaller than 2 + 2, so you leave it unchanged and mark 2 as visited. Then you go to 1, but since it has no unvisited neighbors, you mark it as visited and you are done. The shortest distance to 2 is 2 and to 1 is 3.

In Prim's algorithm, you first add an edge {2, 3}. In the next step, you could add either {1, 2} or (1, 3}, but since the former is shorter, you add it and you are done.

3. Yeah, with the Dijsktra spanning tree, this was why i was getting so confused, because as far as i was concerned, Dijkstra shouldnt be producing a spanning tree! But the question still asked for one.

This animation showed a spanning tree too

Dijkstra's Algorithm Animated