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
8	inf	inf	inf	3	3	inf	inf	12
8	inf	inf	6	3	3	7	inf	6
6	inf	inf	6	3	3	7	inf	6
6	inf	22	6	3	3	7	inf	6
6	inf	22	6	3	3	7	inf	6
6	24	22	6	3	3	7	26	6
6	24	22	6	3	3	7	26	6
6	24	22	6	3	3	7	26	6
6	24	22	6	3	3	7	26	6

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

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
8	inf	inf	inf	3	3	inf	inf	12
8	inf	inf	6	3	3	7	inf	6
6	inf	inf	6	3	3	7	inf	6
6	inf	22	6	3	3	7	inf	6
6	inf	22	6	3	3	7	inf	6
6	24	22	6	3	3	7	26	6
6	24	22	6	3	3	7	26	6
6	24	22	6	3	3	7	26	6
6	24	22	6	3	3	7	26	6

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
8	inf	inf	inf	3	3	inf	inf	12
8	inf	inf	6	3	3	7	inf	6
6	inf	inf	6	3	3	7	inf	6
6	inf	22	6	3	3	7	inf	6
6	inf	22	6	3	3	7	inf	6
6	24	22	6	3	3	7	26	6
6	24	22	6	3	3	7	26	6
6	24	22	6	3	3	7	26	6
6	24	22	6	3	3	7	26	6

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
8	inf	inf	inf	3	3	inf	inf	12
8	inf	inf	6	3	3	7	inf	6
6	inf	inf	6	3	3	7	inf	6
6	inf	22	6	3	3	7	inf	6
6	inf	22	6	3	3	7	inf	6
6	24	22	6	3	3	7	26	6
6	24	22	6	3	3	7	26	6
6	24	22	6	3	3	7	26	6
6	24	22	6	3	3	7	26	6