Tensor's blog

By Tensor, 10 years ago, In English
  • have been trying this problem but in vain .

here is my code so far. I have considered the graph as DAG.

any help plese. thanks in advance

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

The first thing to notice is that you will use at most N-1 edges, otherwise you would create a cycle and that wouldn't be a shortest path, because you could eliminate the cycle from the path and that would result in a shorter one. So now we have at most 150 nodes and 150 edges for query.

Second, if we are at a node X coming from a path with Y edges, we can go to any adjacent node of X using a path with Y+1 edges.

How can we use this in our advantage?

Let's sort the edges by increasing weight and try to relax all of them in this order; each time we relax an edge (u,v) we are getting the shortest path to v using only an increasing path, because the edges we've relaxed so far have a small weight.

But there is still the issue of the amount of edges used, so we can consider each node being a pair <node,num_edges>, then we try to relax all <u,x>, 0 <= x < n-1, reaching all <v,x+1>.

We can notice that if one query starts at node A, any other query that also starts at node A will have already been computed, so we can save the result of each query for further use.

When the relaxing is done, we can see all <B,x>, 0 <= x <= c, and get the small distance.

I'm not sure if I've made myself clear, so feel free to ask anything.

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

    thank you for explanation, if you don't mind what do you mean by sorting all edges?

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

      I mean that instead of creating a graph just store the edges in an array/vector, then sort them by increasing weight.

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

        thank you very much. I'll try to implement this idea :-)