Data Structures and Algorithms -- CSCI 230
Chapter 9 -- Review Solutions

1.

Dijsktra's algorithm computes the shortest length (minimum cost) path from a starting vertex to each of the other vertices in a graph. There may, however, be more than one shortest path. Explain in words, not in pseudocode, how to modify Dijkstra's algorithm to produce a count of the number of shortest length paths from the start vertex to each of the other vertices.

Solution:
First, for each vertex, record the count of the minimal length paths. Initialize this count to 1 for the start vertex. Second, when a new shortest path to vertex w is found, which passes through vertex v, the count for w should be set equal to the count for v. Third, if a new, but equal length path to vertex w is found, which passes through vertex v, the count for v should be added to the count for w. These are the only changes necessary.

2.

Dijsktra's algorithm computes the shortest length (minimum cost) path from a starting vertex to each of the other vertices in a graph. There may be, however, more than one shortest path. Suppose that among these equal distance shortest paths, you wanted the algorithm to pick the path having the fewest edges. Explain carefully in words, not in pseudocode, how to modify Dijkstra's algorithm to do this.

Solution:

(a)

For each vertex, record the number of edges in a new variable called count. Initialize count to 0 for the start vertex.

(b)

When a new shortest path to vertex w is found, which passes through vertex v, set w.count = v.count+1.

(c)

If a new, but equal length path to vertex w is found, which passes through vertex v, change the path to be the one through v if v.count < w.count-1. Set w.count = v.count+1.

3.

(a)

Find a topological sort of the following directed acyclic graph. You need only list the vertices in order, although showing your work will help earn partial credit if you make a mistake.

Solution: Here are the six different possibilities:

6, 5, 4, 2, 7, 3, 1
6, 5, 4, 7, 2, 3, 1
6, 5, 4, 7, 3, 2, 1
6, 5, 7, 3, 4, 2, 1
6, 5, 7, 4, 3, 2, 1
6, 5, 7, 4, 2, 3, 1

(b)

This graph has more than one topological sort. Briefly describe the general structure of directed acyclic graphs that have exactly one topological sort.

Solution: Any directed acyclic graph where there is a single path joining all the vertices. There may be more edges, as long as they don't form a cycle. Thus, it is not enough to say that the graph is a chain of edges.