dijkstra - Multi-source single destination algorithm -
i have graph need find distances multiple sources single destination. know how find single source multi destination using dijkstra's algorithm.
i found accepted answer here: algorithm bellman-ford, multiple start, single destination?
but don't understand why work. can explain why answer works?
it works because if have (original) source s, , target t - in modified graph, reverse edges , find shortest path t nodes, including s.
this path t->v1->v2->...->vk->s
each edge (u,v) in path exist if , if there edge in original graph (v,u), above path in reversed graph can directly translated path:
s->vk->vk-1->...->v2->v1->t the weight of paths identical, , there no shorter path, otherwise - have found on reversed graph.
as side note, prefer transform multiple source problem single source problem creating new dummy node x, , create edge x of sources weight 0, , run shortest path algorithm x source.
(assuming need shortest path source target)
Comments
Post a Comment