# Difference between revisions of "TADM2E 6.7"

From Algorithm Wiki

(→Part B) |
|||

(One intermediate revision by the same user not shown) | |||

Line 8: | Line 8: | ||

No. Example would be the following graph: | No. Example would be the following graph: | ||

− | A -1 | + | <pre> |

− | B -1 | + | A -1 B |

− | A - | + | B -1 C |

+ | A -1 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 |

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