How many topological orders are there for the following directed acyclic graph (given in Python format)? List them all.
{ 0:[1,2], 1:[3], 2:[4], 3:[5], 4:[5], 5:[] }
In the "Example of finding critical path" slide from the lecture notes, suppose that you are allowed to speed up exactly one activity (the blue arrows in the example), but you have to pay $1000 for each day of speedup (for instance, speeding up an activity by two days would cost $2000). Which activity should you speed up in order to get the project done as quickly as possible, what is the minimum total time you can achieve, and what is the minimum cost to obtain this time?
Suppose that we wish to find paths that minimize the product of edge weights, instead of the sum. Assume that all weights are positive.
Give a modified form of the pseudocode for the relax procedure, from the "Relaxation algorithms (more detail)" slide of the lecture notes, that handles this product minimization variation of shortest paths.
For minimizing the sum of edge weights, Dijkstra's algorithm will work whenever all edge weights are non-negative numbers. What is the corresponding condition on edge weights that allows Dijkstra's algorithm to be used with your modified relaxation procedure from part (a) to minimize the product of edge weights?
Let \(G\) be a directed graph for which all edge weights are positive, with a specified target vertex \(t\). Define the "detour cost" of a directed edge \(u\to v\) to be the amount of additional distance that you would travel to get to \(v\) along a path that uses edge \(u\to v\) and then follows a shortest path, compared to the distance that you would travel directly along a shortest path to \(t\).
Write a formula for the detour cost, in terms of the length of edge \(u\to v\) and the distances from \(u\) and \(v\) to \(t\).
Describe how to find a system of heights with the following property: reweighting the graph using your heights replaces each edge weight by its detour cost. (Hint: compare the formula from part (a) to the formula for reweighting edges.)