TADM2E 6.7

From Algorithm Wiki
Revision as of 00:48, 1 August 2020 by Matt (talk | contribs) (Undo revision 1089 by FuckMatt (talk))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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