KyRillos_BoshRa's blog

A hard shortest path problem

By KyRillos_BoshRa, history, 6 years ago, In English

I am trying to solve this problem for a while now but I can't come up with solution better than SPFA from every node which (for sure) gives TLE. so can you help finding a faster solution? thanks in advance.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bellman-Ford?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    SPFA is faster than Bellman-ford and it gives TLE :(

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    actually SPFA is an improvement of the Bellman–Ford algorithm

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

      Oh, I see. I think I read the problem wrong.

      Another idea: Assuming d[u][v] <= d[u][w] + d[w][v] holds, we can simply do a Bellman-Ford (or SPFA if you want) from vertex 1 to all other vertices in O(nm) and find pairs of distances in O(n^2) since we can rearrange the inequality to be d[w][v] >= d[u][v] — d[u][w], therefore all of the answers we gathered are valid. I'm guessing the condition still holds under negative edge weights as well, after you've removed the possibility of a negative cycle.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I'm sorry but I can't get your idea well.How doing Bellman-ford only from vertex 1 will guarantee finding the answer.

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

        With this assumption the answer would be the minimum edge weight in the graph

        → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

The answer is not going to be <insert shortest paths algorithm here>, that would be boring.

Maybe this gives TLE but here is what I would do. First, let's check if there is a negative cycle. If so, output -inf. Now, let dp[u] denote the length of the shortest path that ends with the vertex u. To calculate dp[u] we do this:

initially dp[u] = inf for all u
repeat M times
    for all edges u->v:
        dp[v] = min(dp[v], dp[u] + cost(u, v))

Now, output the minimum of dp[u] over all vertices u.

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

    thanks this is very nice approach actually. I think you may want to add dp[v] = min(dp[v], cost(u, v)) first. any way I got the idea thanks alot.

    → Reply