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

Time: O(E + V)

#### #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. ### #Algorithm 3: Bellman-Ford Algorithm

Work for `Negative Weights without negative weighed cycle`

Dijkstra Algorithm no longer works! #### #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! Time: O(E * V)

### #Cost Summary for 3 Algorithms: ### #Reference

All pictures credited to Princeton Algorithm Course