cs2010_AY1415S1_final

[0WN463]

Let the edge (a, b) be the edge with the minimum weight over all other edges in the graph G.
The shortest path from source vertex a to destination vertex b must definitely pass through
this edge (a, b). Note: There may be other possible paths from vertex a to vertex b in G.

4. True. If there is a shorter path, there is at least one more shorter edge. Contrafiction.

But if a - b is -2, and a-c, c-d, d-e, e-b are all -1, then the long bridge would give a distance of -3
I think it's true for positive weights though

5. Suppose that a Directed Acyclic Graph (DAG) G has X different topological orders. If we delete
   a single edge of G, the resulting graph G’ will definitely has > X different topological orders.

6. False. If anything, it will have LESS number of toposorts.

If the graph is just a->b. the topo sort is a,b. But if you delete the only edge, the topo sort becomes a,b or b,a

[Psyf]

4. You are right. I did not take into account negative weights.
5. The problem I have is with the word DEFINITELY. We can construct cases, but it's not always the case.