CODEWITHSUNDEEP
algorithmgraph-theorynpmax-flow
Vishal Jain
Vishal Jain

Reputation: 21

Disconnect two nodes in undirected weighted graph with min cost

Suppose we have given an undirected weighted graph and a source and destination node we need to disconnect the source and destination node by removing the edges and the cost of removing the edge is the weight for an edge. We need to minimize the cost to disconnect two nodes.

For Example

enter image description here

here to disconnect the 0 node and 6 node it required 5 min cost

Upvotes: 2

Views: 431

Answers (2)

Max Ostrowski
Max Ostrowski

Reputation: 623

With Answer Set Programming you can efficiently solve NP problems declaratively.

Given an instance file instance.lp to describe your graph:

edge(0,1,5).
edge(1,2,3).                             
edge(2,5,3).                   
edge(5,6,4).
edge(1,3,4).           
edge(3,4,5).          
edge(4,6,6).                                                   
                                                      
source(0).                      
sink(6).

and an encoding.lp that describes your problem:

%% chose a subset of the edges to remove 
{removed(X,Y,W) : edge(X,Y,W)}.
            
%% source is reachable 
reach(X) :- source(X).
%% going through edges is reachable if the edge ws not removed 
reach(Y) :- reach(X), edge(X,Y,W), not removed(X,Y,W).
%% handling bidirectional edges 
reach(Y) :- reach(X), edge(Y,X,W), not removed(Y,X,W).
                                                                                                                       
%% it is not allowed to reach the sink                                                                                 
:- sink(X), reach(X).                                                                                                  
                                                                                                                       
%% minimize the number of removed edges weighted by W                                                                  
#minimize {W,X,Y : removed(X,Y,W)}.                                                                                    
                                                                                                                       
%% show only removed edges                                                                                             
#show removed/3.

The call clingo encoding.lp instance.lp (available at https://potassco.org/ ) produces the output:

clingo version 5.5.1
Reading from encoding.lp ...
Solving...
Answer: 1
removed(5,6,4) removed(4,6,6)
Optimization: 10
Answer: 2
removed(5,6,4) removed(1,3,4)
Optimization: 8
Answer: 3
removed(0,1,5)
Optimization: 5
OPTIMUM FOUND

The last answer being the optimal solution to your problem. You can also simply copy the contents of the two files into your browser textfield to try it out here (with reduced performance).

Upvotes: 1

ravenspoint
ravenspoint

Reputation: 20596

LOOP
   Use Dijkstra to find min path from src to dst
   If no path found
      STOP
   Remove cheapest link on path

Upvotes: 0

Related Questions