How to understand the tree with shortest path(Dijkstra algorithm)?

Question

I understand the minimum spanning tree (Kruskal's algorithm), however, the shortest path where a specified node is stated (Dijkstra's algorithm) seems a bit confusing. How would I solve the problem below?

Question: For the graph above, find the tree of all shortest paths starting at vertex 1.

Could someone please explain how to solve this problem step-by-step? It would be greatly appreciated!

Answer 1

You start at vertex $1$ and consider all edges starting at $1$. There are five different ones (to vertices $4$,$2$,$8$,$3$,$10$). You choose the shortest one, namely to vertex $4$ (with weight $3$), and add it to your tree. Now it is important to see that there is no possibility to get a shorter path from vertex $1$ to vertex $4$ as all weights are non-negative (or even positive here). We chose the shortest possible path, so as soon as we choose another one, it will be longer.

Now we repeat this process. Again we take a look at all the possible paths from vertex $1$. However, this time we can also go to vertex $8$ (with total weight $3+1=4$), vertex $3$ (with total weight $3+6=9$) and vertex $5$ (with total weight $3+10=13$). Again we choose the shortest path from $1$ to any other NEW vertex (we do not have to find a new path to a vertex we have already visited because we know that the new path cannot be shorter). The next edge we will choose to add is from vertex $4$ to vertex $8$ (because it has minimal weight $4$). We repeat this until we have a path to all vertices.

A bite more algorithmically:

1. Mark vertex $1$ as visited.
2. Until all vertices are visited do:
   3. Choose an edge $e$ from a visited vertex to an unvisited vertex $v$ such that the overall length of the path from vertex $1$ to $v$ is minimal (i.e. minimal amgonst all the other paths from vertex $1$ to any other unvisited vertex $v'$).
   4. Mark vertex $v$ as visited.