CMPS 144L Lab Activity
Single-source Uniform-cost Shortest Paths

            

Name______________________
vertexhas edges to
03, 7
12, 9
21, 9
31, 4, 5, 8
42, 8
52, 7, 9
62, 5
72, 6
87
93
The distancesFrom() method uses a queue for the purpose of computing the distances from a specified "source" vertex to each of the other vertices in a given directed graph. To the left is a description of a directed graph having vertices numbered 0 through 9.

Apply the distancesFrom() method to the graph twice, once using vertex 4 as the source and another time using vertex 1 as the source.

Each time, show your work by filling in the missing details in the figures below. As you will recall from lecture, IDs of vertices reachable from the source vertex should be placed into the "queue" row going from left to right in the order that they are inserted into the queue. The "enq" and "deq" rows are to indicate, for each such vertex, at which points in time it was inserted/removed from the queue. Points in time are numbered 1, 2, 3, etc., etc. The dist array should be filled in with the final values of its elements. 
      +----+----+----+----+----+----+----+----+----+----+
      |    |    |    |    |    |    |    |    |    |    |
queue | 4  |    |    |    |    |    |    |    |    |    |
      +----+----+----+----+----+----+----+----+----+----+

enq    _1__ ____ ____ ____ ____ ____ ____ ____ ____ ____

deq    _2__ ____ ____ ____ ____ ____ ____ ____ ____ ____ 
        0    1    2    3    4    5    6    7    8    9
     +----+----+----+----+----+----+----+----+----+----+
     |    |    |    |    |    |    |    |    |    |    |
dist |    |    |    |    |  0 |    |    |    |    |    |
     +----+----+----+----+----+----+----+----+----+----+

      +----+----+----+----+----+----+----+----+----+----+
      |    |    |    |    |    |    |    |    |    |    |
queue | 1  |    |    |    |    |    |    |    |    |    |
      +----+----+----+----+----+----+----+----+----+----+

enq    _1__ ____ ____ ____ ____ ____ ____ ____ ____ ____

deq    _2__ ____ ____ ____ ____ ____ ____ ____ ____ ____ 

        0    1    2    3    4    5    6    7    8    9
     +----+----+----+----+----+----+----+----+----+----+
     |    |    |    |    |    |    |    |    |    |    |
dist |    |  0 |    |    |    |    |    |    |    |    |
     +----+----+----+----+----+----+----+----+----+----+