search

Psyf / DataStructsAndAlgos-2040C

Sorting Algorithms taught int 2040C implemented
3 stars 4 forks source link

cs2010_AY1415S1_final #10

Open 0WN463 opened 6 years ago

0WN463 commented 6 years ago

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.

  1. 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

  1. 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.

  2. 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 commented 6 years ago
  1. You are right. I did not take into account negative weights.
  2. The problem I have is with the word DEFINITELY. We can construct cases, but it's not always the case.