hardy_9795's blog

Help needed in a graph problem
By hardy_9795, history, 4 years ago, In English

We have been given a graph such that a path exists between any two given nodes.The edges have some weight assigned to them. We are given a starting node and a ending node and we required to find the minimum distance between two nodes.The distance is the sum of edge weights. We have a special power by which we can change the weights of atmost k edges, we can make their weight to be equal to zero. So given two nodes we are supposed to find the minimum distance between them using the special power atmost k times.

  • Vote: I like it
  • -13
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Can you provide the link to the original problem?

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Graph is a tree => unique path between any 2 nodes. You just need to determine the path between the given nodes and take the weight of k "heaviest" edges in the path to be 0.

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

First root the tree on any one vertex U or V then find the parent array p[i] then you can traverse from U to V and then make all heaviest K edges equal to zero and find the sum of remaining edges.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    Consider an example graph- (1 2 2), (1 3 2), (2 4 2), (4 5 1), (3 5 7), Consider it as (u,v,w) i.e. edge between u and v with weight w. And also suppose k=1 and we need path from node 1 to node 5. Now can you tell what will be the correct approach according to this example. All edges are undirected.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hardy_9795 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

The graph was not a tree sorry for the mistake.Now can someone tell the approach.It is guaranteed that there is a path between the two required nodes.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is why you provide a link to the original problem.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually i don't have the link as it was part of an internship exam and we were not supposed to take the screenshots.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

Sorry! Wrong approach

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider a graph where there is a path of k+1 edges of weight 1 from the source to the destination, and also an edge from the source to the destination of weight k+2. In this graph your approach will pick the path of k+1 edges, ignore k of them, so the cost will be equal to 1. But it is optimal to set the weight of the heaviest edge to 0, so that the minimal cost is equal to 0.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes,this is the same mistake that was present in my solution also.Can you tell the correct way of solving this problem.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh my, you are right! I didn't think of that.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I implemented the same solution but it will fail. Consider an example graph- (1 2 2), (1 3 2), (2 4 2), (4 5 1), (3 5 7), Consider it as (u,v,w) i.e. edge between u and v with weight w. And also suppose k=1 (the no. of times we can use the special power) and we need path from node 1 to node 5. Now can you tell what will be the correct approach according to this example. All edges are undirected. In this example the correct answer is 2 but your logic will give 3.

    → Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I don't really know how to solve this if V, E and K are relatively big, but i have an idea that works in O((V+E)*K*log(V)).

If k=0, we just use dijkstra to generate the array dist[x] and the answer is dist[destination]. For k>0, let's give the array dist a second dimension, so that dist[x][y] represents the shortest path to x from the source, which sets the weight of y edges to zero. Now the answer for our problem is the minimum of all dist[destination][y]. We can calculate this array with a modified dijkstra, because now if we are currently in a node x to which we got by setting y edges to 0, for each outgoing edge to a node z we have two options:

we don't set this edge weight to 0, in this case we will change dist[z][y]

or we set this edge weight to 0, so we change dist[z][y+1]

You can think of this as duplicating the original graph into k+1 layers, and for each edge, adding an edge of cost 0 from each layer i to i+1, in this way if we calculate the shortest path from the source in layer 0, to the destinations in each layer, we will get the shortest paths that set 0, 1, 2 . . . k edges to 0.

→ Reply