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	inf	inf	inf	18	19	inf	inf
inf	27	32	34	inf	18	19	31	inf
inf	27	32	34	inf	18	19	31	inf
inf	27	32	34	inf	18	19	31	46
51	27	32	34	inf	18	19	31	32
51	27	32	34	inf	18	19	31	32
51	27	32	34	35	18	19	31	32
51	27	32	34	35	18	19	31	32
51	27	32	34	35	18	19	31	32

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

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
inf	inf	inf	inf	inf	18	19	inf	inf
inf	27	32	34	inf	18	19	31	inf
inf	27	32	34	inf	18	19	31	inf
inf	27	32	34	inf	18	19	31	46
51	27	32	34	inf	18	19	31	32
51	27	32	34	inf	18	19	31	32
51	27	32	34	35	18	19	31	32
51	27	32	34	35	18	19	31	32
51	27	32	34	35	18	19	31	32

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
inf	inf	inf	inf	inf	18	19	inf	inf
inf	27	32	34	inf	18	19	31	inf
inf	27	32	34	inf	18	19	31	inf
inf	27	32	34	inf	18	19	31	46
51	27	32	34	inf	18	19	31	32
51	27	32	34	inf	18	19	31	32
51	27	32	34	35	18	19	31	32
51	27	32	34	35	18	19	31	32
51	27	32	34	35	18	19	31	32

1	2	3	4	5	6	7	8	9
inf	inf	inf	inf	inf	inf	inf	inf	inf
inf	inf	inf	inf	inf	18	19	inf	inf
inf	27	32	34	inf	18	19	31	inf
inf	27	32	34	inf	18	19	31	inf
inf	27	32	34	inf	18	19	31	46
51	27	32	34	inf	18	19	31	32
51	27	32	34	inf	18	19	31	32
51	27	32	34	35	18	19	31	32
51	27	32	34	35	18	19	31	32
51	27	32	34	35	18	19	31	32