Difference between revisions of "TADM2E 6.7"
From Algorithm Wiki
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
