Timeline for Multiple source shortest path with one reversal
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 13, 2017 at 13:13 | comment | added | sbzk | Being the same in principle, its just an alternate view of the above described solution. | |
| Feb 13, 2017 at 13:12 | comment | added | sbzk | An alternate simpler view would be to use the standard dijikstra's algorithm with an extra flag field stored along with each vertex label. This flag would indicate whether the reverse edge have been used yet (flag=1) or not (flag=0), to build the shortest path to the vertex. Hence, when a vertex is added with shortest distance from $s$, you allow two such instances to be processed one with flag 0, and one with flag 1. And whenever a vertex with flag 0 is processed, you also consider reverse edges pushing the entries of corresponding neighbours in the heap with flag 1. | |
| Feb 12, 2017 at 21:40 | history | answered | Mikhail Rudoy | CC BY-SA 3.0 |