Dijkstra's shortest path algorithm

Explanation of the shortest path tree

The table below shows the shortest path tree from node 0 to all other nodes in the graph. In each iteration, a new node is added to the tree, and the distance to that node from all nodes adjacent to it are updated. The shortest path from a node to the source node 0 is entirely within this (growing) tree. Refresh the page to see another randomly generated unweighted graph.

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
inf	inf	13	inf	inf	17	17	2	inf
3	inf	13	inf	6	17	17	2	inf
3	inf	13	13	6	17	17	2	17
3	inf	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	29	13	12	6	17	17	2	16

The order in which the shortest paths are added: 0, 8, 1, 5, 4, 3, 9, 6, 7, 2.

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
inf	inf	13	inf	inf	17	17	2	inf
3	inf	13	inf	6	17	17	2	inf
3	inf	13	13	6	17	17	2	17
3	inf	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	29	13	12	6	17	17	2	16

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
inf	inf	13	inf	inf	17	17	2	inf
3	inf	13	inf	6	17	17	2	inf
3	inf	13	13	6	17	17	2	17
3	inf	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	29	13	12	6	17	17	2	16

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
inf	inf	13	inf	inf	17	17	2	inf
3	inf	13	inf	6	17	17	2	inf
3	inf	13	13	6	17	17	2	17
3	inf	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	30	13	12	6	17	17	2	16
3	29	13	12	6	17	17	2	16