Difference between revisions of "TADM2E 6.7"
From Algorithm Wiki
(Redirected page to UNTV) |
|||
| Line 1: | Line 1: | ||
| − | + | === 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: | ||
| + | |||
| + | <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
