CPSC 220 Fall 2005
HW 17: Shortest Paths

Read the first two paragraphs in "Determining the Shortest Path" on pp. 559-560 of the text. These paragraphs describe an algorithm based on BFS for finding the shortest path from one vertex to another in an unweighted graph.

Example

Consider the graph below:

  V = {A,B,C,D,E}

  E = {(A,B),
       (A,C),
       (B,D),
       (C,D),
       (D,E)}

To find the shortest path to every other vertex from A, you simply do a BFS from A but when each vertex is visited also record its predecessor (the vertex the visiting edge came from) and the length of the path to this node (which is 1 more than the length of the path to its predecessor). We can keep the necessary information in a table with the following columns:

Visited   Pred   Pathlength  
-------   ----   ----------

To begin with we put A in the queue and visit it. It has no predecessor and the length of the path to A from A is 0, so we record this information:

Queue: A

Visited   Pred   Pathlength  
-------   ----   ----------  
  A       none       0

We now dequeue A and enqueue its unvisited adjacent vertices, namely B and C. Recall that in our BFS algorithm we visited each vertex as it was enqueued, so B and C are now visited. The predecessor for both is A, and the length of the path for both is 0+1=1:

Queue: B C

Visited   Pred   Pathlength  
-------   ----   ----------  
  A       none       0
  B        A         1
  C        A         1

We now dequeue B and enqueue its unvisited adjacent vertices, namely D. We visit D and note its predecessor (B) and pathlength (2):

Queue: C D

Visited   Pred   Pathlength  
-------   ----   ----------  
  A       none       0
  B        A         1
  C        A         1
  D        B         2

We now dequeue C and enqueue its univisited adjacented vertices, but there are none (as D has already been visited). So we dequeue D and enqueue its univisited adjacented vertices, namely E:

Queue: E

Visited   Pred   Pathlength  
-------   ----   ----------  
  A       none       0
  B        A         1
  C        A         1
  D        B         2
  E        D         3

The list of visited vertices is now equal to V, so we are finished. We can now compute the path to each vertex by unwinding the predecessors:

Queue: E

Visited   Pred   Pathlength  Path
-------   ----   ----------  ----
  A       none       0        --
  B        A         1        AB
  C        A         1        AC
  D        B         2        ABD
  E        D         3        ABDE

Problem

Now consider the graph below:

  V = {A,B,C,D,E,F,G,H}

  E = {(A,B),
       (A,D),
       (B,C),
       (B,D),
       (B,F),
       (B,G),
       (C,E),
       (D,F),
       (D,G),
       (E,D),
       (E,H),
       (G,E),
       (G,F)}

Use the algorithm above to find the shortest path from A to every other vertex. Fill out the chart below as you proceed -- when you visit each vertex put it in the "Visited" column, its predecessor in the "Pred" column, and the length of the path to the vertex in the "Pathlength" column. (Remember that in our BFS algorithm we visited each vertex when we put it in the queue.) When the algorithm is complete, go back and figure out the path to each vertex by tracing back through the predecessors.

Visited   Pred   Pathlength  Path
-------   ----   ----------  ----

CPSC 220 Fall 2005HW 17: Shortest Paths

Example

Problem

CPSC 220 Fall 2005
HW 17: Shortest Paths