Difference between revisions of "TADM2E 6.7"
From Algorithm Wiki
m (→Part B) |
(→Part B) |
||
| Line 9: | Line 9: | ||
<pre> | <pre> | ||
| − | A -1 | + | A -1 B |
| − | B -1 | + | B -1 C |
| − | A - | + | A -1 C |
</pre> | </pre> | ||
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 -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
