justHusam's blog

2 shortest paths ( disjoint paths )
By justHusam, 9 years ago, In English

Given a weighted, undirected graph. How I can find 2 paths from S to T, such that they don't share any edge (but may share some nodes), and sum of their lengths must be minimal possible ??

Edit: The problem has been solved using Minimum-cost flow. Thanks for Govikhuu

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

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

It is mincost-maxflow problem. All edge must have 1 unit capacity and edge weight is cost of using that edge. Then you can simply find minimum cost of 2 unit flows.

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

    Can you explain your algorithm in more details please ?

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

It is a problem from the running contest — Bubble Cup. Link

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

    I don't know any thing about this contest. I'm trying to solve this problem from UVa (10806 — Dijkstra, Dijkstra.).

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

    That was my first thought. Even if he's truly not solving that problem, I think waiting before posting the solution would be nice. I'm sure there are quite a few people here on Codeforces that participate in BubbleCup.

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

      Excuse me, I appreciate your opinion. :) But I want to continue my practice and solve this problem! Any one who are participating in this contest must be honest with himself and try to solve the problems without any cheating.

      → Reply