Modified Minimum Spanning Tree

user_15565478 0
Viewed 291

I have to implement an algorithm where we have an existing road network (nodes connected by path ie., undirected graph). We have to connect all the cities together, and normally I would use something like Kruskal's algorithm to get a minimum spanning tree.

However, we do not care how long it takes to go between cities (can assume the edge weights are all 0 or 1 or something), rather there is a cost associated with building a road (adding an edge between 2 vertices) or destroying a road (deleting an edge between 2 vertices). This is the only cost we have to consider. Our goal is to ONLY have 1 path connecting each pair of cities. All costs are non-negative integers.

I have 3x 2d arrays (I have represented them as a matrix below, with the row and columns being the cities numbered from 0,1,2...,etc.)

Country[i][j]=1 or 0: there is an existing road between city i and j if and only if country[i][j]=1.

  0 1 2
0 0 1 1
1 1 0 1
2 1 1 0

Build[i][j]: the cost for building a road between i and j

  0 1 2
0 0 1 3
1 1 0 2
2 3 2 1

Destroy[i][j]: the cost for destroying a road between i and j.

  0 1 2
0 0 1 3
1 1 0 2
2 3 2 1

I'm not sure how to go about this, any sort of guidance would be appreciated

shortest-path kruskals-algorithm minimum-spanning-tree algorithm
1 Answers

You can solve it with two observations:

  1. It's kind of obvious that the optimal solution is a tree and if an edge is destroyed, then that edge was part of the initial graph. So in an optimal solution, let's add the destroyed edges one by one. Let's say we are adding the destroyed edge e1, then a cycle is formed and if there exists an edge e2 that was previously built and belongs to that cycle, then an alternative optimal solution can be created by not destroying the edge e1 and not building the edge e2. If no cycle was formed with that property the edge e1 is skipped and an alternative optimal solution will be tested with the next destroyed edge. This procedure is repeated until every destroyed edge is tested

  2. Let's focus on an initially connected component C, if the problem were only that component C then we can get an optimal solution by running Kruskal to get the heaviest spanning tree, having as weight function the destroying-edge cost matrix. Moreover, we can say that any optimal solution for C belongs to some general optimal solution for the initial graph. Why?, well, after applying step 1, two nodes of C can't be connected with a path that have built edges.

So the algorithm is:

  • Find the total cost to get the heaviest spanning tree in each connected component as was mentioned in step 2.

  • Create a new graph by compressing connected components and find the cheapest cost of building new edges to connect all these nodes (Hi classic Kruskal!).

    *For implementation you can ommit create that graph, just run classic Kruskal after having created your spanning trees for each connected component.

user_163214910
Related