Shortest Path Algorithm
#Algorithms
 Dijkstra (Nonnegative weights)
 Topological Sort (No directed cycles)
 BellmanFord (No negative cycles)
#Algorithm 1: Dijkstra
Only work for nonnegative weighed graph (Not necessarily acyclic)
.
#Dijkstra vs Prim
They are essentially the same
algorithm.
 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).
#Performance
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
#Performance
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
Solution:
 Create an edgeweighted 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.
A 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.
 有weight的都是每一个Job的Duration.
所以比如下图这种情况：
要保证每个Job都完成的话，只能取longest path而不是shortest path.
#Algorithm 3: BellmanFord Algorithm
Work for Negative Weights without negative weighed cycle
Dijkstra Algorithm no longer works!
这个slides里的内容很有意思. 先是举例子说明了为什么Dijkstra Algorithm不能在Negative weighted graph上work.
然后可能有人会想出上面Reweighting的trick. 但是这样的想法是错误的，因为即使这样得到了一个positive weighted graph, 但是shortest path就不是原来那条了!
#Negative Cycle
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 BellmanFord algorithm, if any vertex v is updated in phase v, there exists a negative cycle.
#Negative cycle application: Arbitrage Detection
#Algorithm
 Initialize distTo[s] = 0 and distTo[v] = ∞ for all vertices.
Repeat V times:
 Relax each edge
This is a
Dynamic Programming
algorithm!
#Performance
Time: O(E * V)
#Cost Summary for 3 Algorithms:
#Reference
All pictures credited to Princeton Algorithm Course