# Difference between revisions of "TADM2E 6.7"

From Algorithm Wiki

(create page) |
|||

Line 6: | Line 6: | ||

=== Part B === | === 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 |

## Revision as of 20:40, 18 December 2015

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