## 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
------- ---- ---------- ----