1. (3 points) In the digraph below, find the lowest cost path all vertices to vertex 7, using the Dijkstra algorithm in reverse (backwards).
2. (3 points) Design an algorithm for solving the following problem: given a directed acyclic graph (DAG), find a maximum length path in it, in O(n+m).
3. (3 points) Find a minimum spaning tree in the following graph, using the Prim's algorithm:
1. We construct the table with the current vertex, queue, distance to vertex 7, and for each vertex, the next vertex on path to 7
| x | q | d | next | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| 7 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | - | - | - | - | - | - | - | |
| 7 | 2,5 | ∞ | 12 | ∞ | ∞ | 5 | ∞ | 0 | - | 7 | - | - | 7 | - | - |
| 5 | 2,3,4,6 | ∞ | 12 | 8 | 7 | 5 | 9 | 0 | - | 7 | 5 | 5 | 7 | 5 | - |
| 4 | 1,2,3,6 | 14 | 12 | 8 | 7 | 5 | 9 | 0 | 4 | 7 | 5 | 5 | 7 | 5 | - |
| 3 | 1,2,6 | 14 | 11 | 8 | 7 | 5 | 9 | 0 | 4 | 3 | 5 | 5 | 7 | 5 | - |
| 6 | 1,2 | 14 | 11 | 8 | 7 | 5 | 9 | 0 | 4 | 3 | 5 | 5 | 7 | 5 | - |
| 2 | 1 | 13 | 11 | 8 | 7 | 5 | 9 | 0 | 2 | 3 | 5 | 5 | 7 | 5 | - |
| 1 | 13 | 11 | 8 | 7 | 5 | 9 | 0 | 2 | 3 | 5 | 5 | 7 | 5 | - | |
Finally, we follow the next columns, in the last row, from each vertex to get the path to 7:
2. We use a dynamic programming approach. We associate, to each vertex x, the length of the longest path ending in x. Let's denote it by d[x].
To compute this value, we notice that the longest path to a vertex x is the longest path to a predecessor y of x, plus the edge (y,x), unless x has no predecessors. This leads to the following recurrence relation:
Since d[x] depends on the predecessors of x, it is convenient to compute it in topological sorting order.
The algorithm is then:
Input: G=(X,E) a DAG
Output: p a path of maximum length
x0,...,xn-1 = toposort(G)
for x in X do
d[x] = 0
end for
for i=0,n-1 do
x = xi
for y in Nout(x) do
if d[y] < d[x] + 1 then
d[y] = d[x] + 1
end if
end for
maxLen = -1
for x in X do
if d[x] > maxLen then
maxLen = d[x]
final = x
end if
end for
x = final
p = []
while d[x] > 0 do
p.append(x)
for y in Nin(x) do
if d[y] + 1 == d[x] then
x = y
break
end if
end for
end while
p.append(x)
p.reverse()
3. The following is the sequence of iterations, with the growing tree and the candidate edges to be added: