Shortest Path Algorithm
- Dijkstra (Non-negative weights)
- Topological Sort (No directed cycles)
- Bellman-Ford (No negative cycles)
#Algorithm 1: Dijkstra
Only work for
non-negative weighed graph (Not necessarily acyclic).
#Dijkstra vs Prim
They are essentially the
- Prim’s algorithm picks the closest vertex to the Tree.
- Dijkstra algorithm picks the closest vertex to the Source.
Both of them are trying to find the spanning tree. (Dijkstra is find the shortest path from a source to every other vertices.)
- Prim’s algorithm is for the undirected graph.
- Dijkstra algorithm is for the directed graph (with no negative weights).
Time: O(E * log(V)) for Binary Heap
#Algorithm 2: Topological Sort to Find Shortest Path
Only work for
weighed DAG, either positive or negative weight
#Algorithm of Acyclic Shortest Path
- Topological Sort
- Relaxing based on topological order
Time: O(E + V)
#Longest Path Problem
#Parallel Job Scheduling Problem
Given a set of jobs with durations and precedence constraints, schedule the jobs by finding the start time for each job, so as to achieve the minimum completion time, while respecting the constraints.
This is a longest path problem
- Create an edge-weighted DAG.
- Two virtual vertices representing:
- Source: “Before everything start”
- Destination: “After everything is done”
- Each job will create 2 vertices
- Job start
- Job end
- The weight is the duration
- There will be at least 3 edges for each job (not vertex)
- Job start –> Job end
- Source –> Job start
- Job end –> Destination
- Each constraint is an edge.
critical path is the solution to this problem.
- A critical path is the longest path from source to destination.
- Job和Job之间的先后顺序只会产生一条edge, 但不会有weight. 也就是weight是0.
要保证每个Job都完成的话，只能取longest path而不是shortest path.
#Algorithm 3: Bellman-Ford Algorithm
Negative Weights without negative weighed cycle
Dijkstra Algorithm no longer works!
这个slides里的内容很有意思. 先是举例子说明了为什么Dijkstra Algorithm不能在Negative weighted graph上work.
然后可能有人会想出上面Re-weighting的trick. 但是这样的想法是错误的，因为即使这样得到了一个positive weighted graph, 但是shortest path就不是原来那条了!
A directed cycle whose sum of edge weights is negative.
A shortest path exists if and only if no negative cycle.
- Because an infinite loop on negative cycle will keep decreasing the total weights and “eventually” get a negative infinity.
#How to find negative cycle ?
Using Bellman-Ford algorithm, if any vertex v is updated in phase v, there exists a negative cycle.
#Negative cycle application: Arbitrage Detection
- Initialize distTo[s] = 0 and distTo[v] = ∞ for all vertices.
Repeat V times:
- Relax each edge
This is a
Time: O(E * V)
#Cost Summary for 3 Algorithms:
All pictures credited to Princeton Algorithm Course