Bole_jo_koyal's blog

Help needed in graph question
By Bole_jo_koyal, history, 9 months ago, In English

You are given a weighted directed graph of n nodes and e edges, source vertex and destination vertex
For each edge , output the shortest path between source and destination (-1 if not possible) if that edge is made bi-directional and it's weight is set to 0
n is probably 1e5

Any help would be highly appreciated

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

»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Floyd warshall algorithm would've been fine if n wasn't 1e5. Do you have link to the question? or is it yours?

Also tell us about number of edges and time limit.

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

    Got this from a friend who told this is from some online assessment
    If constraints were lower i think we can simply run Dijkstra e times .

    → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think this works ..

  1. Run Dijkstra twice, one from the source (on the original graph) and one from the destination (on the reversed graph). Store shortest distances from each node to the source and the destination.
  2. Now for every edge say E(x,y) connecting nodes x and y. Making it bidirectional is just merging x and y. So now the shortest path is determined by the minimum among actual min distance b/w source and destination and ( min distance among source to x, source to y + min distance among x to destination, y to destination ).
  3. The optimal route can be one of these 5 cases based on 5 possible cases for the above equation:
    • Actual optimal path from source to destination
    • source -> x + x -> destination
    • source -> x + y -> destination
    • source -> y + x -> destination
    • source -> y + y -> destination
→ Reply
»
9 months ago, # |
← Rev. 5   Vote: I like it -9 Vote: I do not like it

[Deleted]

→ Reply