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	4	6	16	inf	10	11	inf	inf
11	4	6	16	inf	10	11	inf	22
10	4	6	16	inf	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22

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

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
inf	4	6	16	inf	10	11	inf	inf
11	4	6	16	inf	10	11	inf	22
10	4	6	16	inf	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
inf	4	6	16	inf	10	11	inf	inf
11	4	6	16	inf	10	11	inf	22
10	4	6	16	inf	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
inf	4	6	16	inf	10	11	inf	inf
11	4	6	16	inf	10	11	inf	22
10	4	6	16	inf	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22
10	4	6	16	22	10	11	9	22