TheRenaissance's blog

Find 2 shortest paths between 2 vertices
By TheRenaissance, history, 11 years ago, In English

You are given a undirected weighted graph with at most 50000 vertices, 100000 edges and 2 vertices A and B. You have to find 2 paths from A to B that no edge is used twice (but they can have common vertices), and the sum of the length of these 2 paths is minimal.

I'm currently stuck on this problem. Can anyone give me a hint? Thank you.

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

»
11 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Think about Max Flow.

Edit: The constrains are high, you may need Dinic Algorithm.

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

    Sucessive shortest paths should be enough. I don't even know how you can use Dinic with min-cost max-flow, anyway...

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

      I think you don't need min-cost max-flow if at every step you find the shortest augmenting path (I'm not sure if possible using Dinic's).

      Edit: I'm not sure if my method works, if not, min-cost max-flow should be the answer.

      → Reply
      • »
        »
        »
        »
        11 years ago, hide # ^ |
         
        Vote: I like it +1 Vote: I do not like it

        That's what I meant by successive shortest paths (that is actually a solution to the min-cost max-flow problem, so your sentence is equivalent to "we don't need shortest paths, we just need Dijkstra")

        As you need only two of them, you can just run two Dijkstra's and it should fit into time limit quite easily.

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

          Oh, I haven't read about sucessive shortest paths, I'll do it soon.

          Thanks.

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

      Successive shortest path should be the correct answer here.
      Its correctness can also be proved by contradiction.

      Based on the constraints, running 2 O(E lgV) Dijkstra should do. (Well you can do it quicker, but who actually codes Fibonacci Heap)

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

I believe that the only thing making this problem non-trivial is the condition "the sum of the length of these 2 paths is minimal". Try to prove that you can greedily take the shortest path, and the next shortest path (not using any of those edges), and that those sum up to the minimal possible answer. Just my 2 cents.

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it +21 Vote: I do not like it

    I don't think that simply removing the edges and finding the next shortest path is optimal. The problem is actually transformed into max-flow-min-cost but is solved quickly since you're looking for flow of 2 (as mentioned above, successive-shortest path algorithm will find it using two djikstras).

    A simple example:

    In case the red path is the shortest one, you'll be stuck not finding a second path, while there is clearly a possibility to take two disjoint paths :)

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

You can simply first use Dijkstra's and keep track of the edges being made use of. After the shortest path has been found, mark all the used edges and assign them a weight = INF. Now apply Dijkstra's again.

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

Isn't this just a simple application of Suurballe's algorithm? =D

Edit: Codeforces didn't seem to like apostrophes in the URL... -_-

→ Reply