#Algorithms

  1. Dijkstra (Non-negative weights)
  2. Topological Sort (No directed cycles)
  3. 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 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

  1. Topological Sort
  2. Relaxing based on topological order

#Performance

Time: O(E + V)

#Longest Path Problem

1
2
3
4
5
How to find longest path ?
1. Negate all weights. (Since this approach allows negative weights)
2. Run shortest path algorithm
3. Negate weights in the result

#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:

  1. Create an edge-weighted DAG.
  2. Two virtual vertices representing:
    • Source: “Before everything start”
    • Destination: “After everything is done”
  3. 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
  4. 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.

证明:

  1. Job和Job之间的先后顺序只会产生一条edge, 但不会有weight. 也就是weight是0.
  2. 有weight的都是每一个Job的Duration.

所以比如下图这种情况:

要保证每个Job都完成的话,只能取longest path而不是shortest path.


#Algorithm 3: Bellman-Ford Algorithm

Work for 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就不是原来那条了!

#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 Bellman-Ford algorithm, if any vertex v is updated in phase v, there exists a negative cycle.

#Negative cycle application: Arbitrage Detection

#Algorithm

  1. Initialize distTo[s] = 0 and distTo[v] = ∞ for all vertices.
  2. 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

Comments