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

Help needed in graph question
Автор Bole_jo_koyal, история, 4 месяца назад, По-английски

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

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

»
4 месяца назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 .

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

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
→ Ответить
»
4 месяца назад, # |
← Rev. 5   Проголосовать: нравится -9 Проголосовать: не нравится

[Deleted]

→ Ответить