Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

graphdp's blog

How to solve this question?
By graphdp, history, 8 years ago, In English

Find the shortest path between a source node and destination node in a undirected positive weighted graph. given you can add at max one edge between any two nodes which are not directly connected to each other.?

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

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

The first thing to do is to find out if the source and destination are in the same connected components,

1) If they are not, then simply adding an edge between the source and destination with the least possible weight will give the answer.

2) If they are, then adding any edge in that component will create a cycle, which will be of no use. Hence the shortest path between the source and destination will be the answer, which can be computed by bfs.

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

    The given graph is weighted your logic will work fine for unweighted graph but not for weighted graph.

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

      The logic is correct for 1, and for 2 you can use Dijkstra, not bfs.

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

        Counter example:

        Let the graph be 1----2-----3

        with edge weight of 1---2 = 10 and edge weight of 2---3 = 1

        source = 1 destination = 2

        here if we add edge between 1--3 of weight = 1 then shortest path = 2

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

          If I get the question correctly now, this show work. If not, then you have to give the link to the original problem.

          1) If there is not a direct edge (by direct you meant an edge with one end on source and other in destination?) then simply draw an edge between them with minimum weight.

          2) Else, Find a node which is connected to the source but not the destination, (or the destination but not the source) of the minimum possible weight you can and add the edge from that node to the source/destination. In the above case, this would bring the answer to 2.

          3)If all nodes have edges between both source and destination,then calculate and store the shortest paths from each node to source and each node to destination. Let them be source[] and destination[] sorted. Then take the smallest two values from each of those two arrays (if they are the same, then take min (source[0] + destination[1], source[1] + destination[0]). Add an edge between these two nodes.

          → Reply