Difference between revisions of "TADM2E 6.7"

From Algorithm Wiki
Jump to: navigation, search
m (Part B)
Line 8: Line 8:
 
No. Example would be the following graph:
 
No. Example would be the following graph:
  
 +
<pre>
 
A -1-> B
 
A -1-> B
 
B -1-> C
 
B -1-> C
 
A -3-> C
 
A -3-> C
 +
</pre>
  
 
Shortest path from A to C is A->B->C.
 
Shortest path from A to C is A->B->C.
  
 
If we increase all weights by two, shortest path will change to A->C
 
If we increase all weights by two, shortest path will change to A->C

Revision as of 16:44, 30 November 2018

Part A

Probably yes. Using Kruskal's algorithm, you'll still get the same insertion order of edges, regardless of how much you add or subtract from the edge weighting.


Part B

No. Example would be the following graph:

A -1-> B
B -1-> C
A -3-> C

Shortest path from A to C is A->B->C.

If we increase all weights by two, shortest path will change to A->C