Блог пользователя hardy_9795

Автор hardy_9795, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • -13
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Can you provide the link to the original problem?

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

Sorry! Wrong approach

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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.