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
16	inf	inf	inf	inf	inf	8	inf	7
16	inf	inf	inf	inf	inf	8	inf	7
16	inf	13	inf	9	inf	8	inf	7
15	inf	13	13	9	inf	8	15	7
14	22	13	13	9	inf	8	15	7
14	22	13	13	9	inf	8	15	7
14	22	13	13	9	33	8	15	7
14	22	13	13	9	33	8	15	7
14	22	13	13	9	33	8	15	7

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

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
16	inf	inf	inf	inf	inf	8	inf	7
16	inf	inf	inf	inf	inf	8	inf	7
16	inf	13	inf	9	inf	8	inf	7
15	inf	13	13	9	inf	8	15	7
14	22	13	13	9	inf	8	15	7
14	22	13	13	9	inf	8	15	7
14	22	13	13	9	33	8	15	7
14	22	13	13	9	33	8	15	7
14	22	13	13	9	33	8	15	7

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
16	inf	inf	inf	inf	inf	8	inf	7
16	inf	inf	inf	inf	inf	8	inf	7
16	inf	13	inf	9	inf	8	inf	7
15	inf	13	13	9	inf	8	15	7
14	22	13	13	9	inf	8	15	7
14	22	13	13	9	inf	8	15	7
14	22	13	13	9	33	8	15	7
14	22	13	13	9	33	8	15	7
14	22	13	13	9	33	8	15	7

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
16	inf	inf	inf	inf	inf	8	inf	7
16	inf	inf	inf	inf	inf	8	inf	7
16	inf	13	inf	9	inf	8	inf	7
15	inf	13	13	9	inf	8	15	7
14	22	13	13	9	inf	8	15	7
14	22	13	13	9	inf	8	15	7
14	22	13	13	9	33	8	15	7
14	22	13	13	9	33	8	15	7
14	22	13	13	9	33	8	15	7