Webwhompers

The algorithm below states more formally the steps of the computation illustrated above.

Distance Algorithm:

Input:

• Undirected graph G=(V,E) with |V|>1
• Source node s
• Destination node t

Output:

• Distance from s to t in G

Steps:

1. if s = t then distance = 0 and we're done; otherwise continue
2. A₀ = {s}
3. B = {x: x∈V and x≠s}
4. i = 1
5. A_i = {x: x is adjacent to at least one node in A_i-1} ∩ B
6. If t∈A_i then distance = i and we're done; otherwise continue
7. If A_i = { } then distance = ∞ and we're done; otherwise continue
8. Remove elements of A_i from set B
9. i = i + 1
10. Go to step5