|
Below is another example that illustrates how to compute distance in a graph. It explicitly counts iterations (of the algorithm we will soon write) and it introduces some more formal bookkeeping: Set Ai = the set of nodes that are distance i from the source node. For example: - A0 is a set with one element: the source node.
- A1 is the set of all nodes adjacent to the source node.
Below we use Ai and a more complicated example to illustrate computing the distances from node 1 to every other node in the graph. Beginning
| 
| Source node = 1
A0 = Set of nodes that are distance 0 from source
={1}
| Iteration 1
| 
| Nodes not yet visited
= all nodes except source
= {2,3,4,5,...,20}
= all white nodes A1 = Set of nodes that are distance 1 from source
= nodes adjacent to source
= {7,14,16,17,20}
= nodes with red arrows pointing at them
| Iteration 2
| 
| Updated set of nodes not yet visited
= {2,3,4,5,6,8,9,10,11,12,13,15,18,19}
= white nodes A2 = Set of nodes distance 2 from source
= unvisited nodes adjacent to any node in A1
= {4,5,8,9,11,13,18,19}
= nodes with red arrows pointing at them | Iteration 3
| 
| Updated set of nodes not yet visited
= {2,3,6,10,12,15}
= white nodes A3 = Set of nodes distance 3 from source
= unvisited nodes adjacent to any node in A2
= {2,6,10,12,15}
= nodes with red arrows pointing at them | Iteration 4
| 
| Nodes not yet visited = {3}
A4 = Set of nodes distance 4 from source
= unvisited nodes adjacent to any node in A3
= {3}
= nodes with red arrows pointing at them | Iteration 5
| 
| Nodes not yet visited = { }
A5 = Set of nodes distance 5 from source
= unvisited nodes adjacent to any node in A4
= { } |
At the end of iteration 5, we see that there are no nodes distance 6 from the source node. Therefore, there are no nodes distance 7 from the source node, no nodes distance 8, etc. Note that if a graph is not connected, then when the algorithm ends, only nodes in the same connected component as the source node will have been visited, and nodes in other components will not have been visited. Nodes that are still unvisited at the end of the algorithm are distance infinity from the source.
|
