the difference happens how we smartly select edge
in the case we Topologically sort the DAG and then select edges in order. since this is dag this works if graph doesn't have cycle and works for negative.
in case of dijkstra we pick the edge that has the minimum priority (in this case d[u], the current shortest distance from source). dijkstra works with cycles but all the weight have to be non negative.
essentially we are starting from all of vertices and relaxing one by one. after the first iteration if there are any edges that can still be relax the graph has negative cycle.
Bi-directional search
alternate forward search from s backward search from t and calculate each df(u) , db(u).
terminate when frontier meets, and find the Minimum value for df(x) +db(x) over all vertices that have been processed in at least one search.
reference == 15. Single-Source Shortest Paths Problem - YouTube
18. Speeding up Dijkstra - YouTube
'Algorithm > Design and Analysis of Algorithms' 카테고리의 다른 글
| Text justification (0) | 2021.01.24 |
|---|---|
| Graph Transform (0) | 2021.01.11 |
| Tree and B-Trees (0) | 2020.12.30 |
| Divide & Conquer: FFT (0) | 2020.12.27 |
| Weighted Interval Scheduling (0) | 2020.12.26 |