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

A hard shortest path problem

Автор KyRillos_BoshRa, история, 6 лет назад, По-английски

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.

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

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

Bellman-Ford?

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    actually SPFA is an improvement of the Bellman–Ford algorithm

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

      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.

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

        → Ответить
»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить