Difference between revisions of "TADM2E 6.7"

From Algorithm Wiki
Jump to: navigation, search
(create page)
 
(Undo revision 1089 by FuckMatt (talk))
 
(4 intermediate revisions by 3 users not shown)
Line 6: Line 6:
 
=== Part B ===
 
=== Part B ===
  
Yes, as long as negative weight edges are not allowed.
+
No. Example would be the following graph:
 +
 
 +
<pre>
 +
A -1 B
 +
B -1 C
 +
A -1 C
 +
</pre>
 +
 
 +
Shortest path from A to C is A->B->C.
 +
 
 +
If we increase all weights by two, shortest path will change to A->C

Latest revision as of 00:48, 1 August 2020

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