hugox14's blog

By hugox14, history, 5 years ago, In English

Hello guys, I am studying graphs and I have the following questions:

If I have an undirected and weighted graph, if the costs of each arc increase by 1:

  • Does the minimum spanning tree change?
  • Do the shortest paths change from vertex $$$v$$$ to others?

Thanks in advance!

  • Vote: I like it
  • +21
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 3   Vote: I like it +23 Vote: I do not like it

The MST won't change, because the relative order of edge weights stays the same. Therefore, by Kruskal's algorithm, the MST will stay the same. Another way to see this is the following: Each spanning tree has n-1 edges. So by increasing each edge weight by 1, the weight of each spanning tree increases by n-1. Would the MST change, the original spanning tree wouldn't have been minimal.

The shortest path can change, however: Consider a graph with 4 vertices and edges (1, 2), (2, 3), (3, 4) of weight 1 and edge (1, 4) of weight 4. Before increasing the edge weights the shortest path from 1 to 4 has length 3 (1-2-3-4). After the increase, the length of this path becomes 6. This is no longer the shortest path, because simply using the edge (1, 4) has length 5. Compared to the spanning trees this issue arrises precisely because shortest paths don't have a fixed number of edges.