Week 4 of Coursera's Algorithms on Graphs

1. Fastest Route.md

1. Fastest Route

1-1. Fastest Route

What is the fastest route to get home from work?

1-2. Naive Algorithm

Observation

Any subpath of an optimal path is also optimal.

Edge Relaxation

• dist[v] will be an upper bound on the actual distance from S to v.
• The edge relaxation procedure for an edge (u, v) just checks whether going from S to v through u improves the current value of dist[v].

Relax((u, v) ∈ E)
  if dist[v] > dist[u] + w(u, v):
    dist[v] ← dist[u] + w(u, v)
    prev[v] ← u

Naive Approach

Naive(G, S)
  for all u ∈ V :
    dist[u] ← ∞
    prev[u] ← nil
  dist[S] ← 0
  do:
    relax all the edges
  while at least one dist changes

Correct distances

Lemma

After the call to Naive algorithm, all the distances are set correctly.

1-3. Dijkstra's Algorithm: Implementation

Pseudocode

  Dijkstra(G, S)
    for all u ∈ V:
      dist[u] ← ∞, prev[u] ← nil
    dist[S] ← 0
    H ← MakeQueue(V) {dist-values as keys}
    while H is not empty:
      u ← ExtractMin(H)
      for all (u, v) ∈ E:
        if dist[v] > dist[u] + w(u, v):
          dist[v] ← dist[u] + w(u, v)
          prev[v] ← u
          ChangePriority(H, v, dist[v])

ExtractMin(H): Find the vertex in H with the minimum dist-value, remove it from H and return this vertex.

1-4. Dijkstra's Algorithm: Running Time

Total running time: T(MakeqQueue) + |V|．T(ExtractMin) + |E|．T(ChangePriority)
Priority queue implementations:

• array: O(|V| + |V|^2 + |E|) = O(|V|^2)
• binary heap: O(|V| + |V|log|V| + |E|log|V|) = O((|V| + |E|)log|V|)

2. Currency Exchange.md

2. Currency Exchange

2-1. Currency Exchange

Problem
You can convert some currencies into some others with given exchange rates. What is the max amount in Russian rubles you can get from 1000 US dollars using unlimited number of currency conversions? Is it possible to get as many Russian rubles as you want? Is it possible to get as many US dollars as you want?

Maximum product over paths

• Input: Currency exchange graph with weighted directed edges ei between some pairs of currencies with weights rei corresponding to the exchange rate.
  
• Output: Maximize ∏︀(j=1 to k) rej = re1re2...*rek over paths (e1, e2, . . . , ek) from USD to RUR in the graph.
  

2-2. Currency Exchange: Reduction to Shortest Paths

Reduction to shortest paths

Use two standard approaches:

• Replace product with sum by taking logarithms of weights
  
• Negate weights to solve minimization instead of maximization
  

Taking the Logarithm

xy = 2^log2(x)*2^log2(y) = 2^(log2(x)+log2(y))
xy → max ⇔ log2(x) + log2(y) → max

Negation

Reduction

Finally: replace edge weights rei by (− log(rei)) and find the shortest path between USD and RUR in the graph.

Solved?

• Create currency exchange graph with weights rei corresponding to exchange rates
  
• Replace rei → (− log(rei))
  
• Find the shortest path from USD to RUR by Dijkstra’s algorithm
  
• Do the exchanges corresponding to the shortest path
  

Where Dijkstra’s algorithm goes wrong?

• Dijkstra’s algorithm relies on the fact that a shortest path from s to t goes only through vertices that are closer to s.
  
• This is no longer the case for graphs with negative edges.
  

2-3. Bellman-Ford Algorithm

Bellman–Ford algorithm

BellmanFord(G, S)
  {no negative weight cycles in G}
  // O(|V|)
  for all u ∈ V : 
    dist[u] ← ∞
    prev[u] ← nil
  dist[S] ← 0
  // |V | − 1 iterations, each O(|E|) => O(|V||E|)
  repeat |V | − 1 times: 
    for all (u, v) ∈ E:
      Relax(u, v)

Running Time

Lemma
The running time of Bellman–Ford algorithm is O(|V||E|).

2-4. Bellman-Ford Algorithm: Proof of Correctness

Lemma
After k iterations of relaxations, for any node u, dist[u] is the smallest length of a path from S to u that contains at most k edges.

Corollary
In a graph without negative weight cycles, Bellman–Ford algorithm correctly finds all distances from the starting node S.

Corollary
If there is no negative weight cycle reachable from S such that u is reachable from this negative weight cycle, Bellman–Ford algorithm correctly finds dist[u] = d(S, u).

2-5. Negative Cycles

Negative weight cycles

Lemma
A graph G contains a negative weight cycle if and only if |V |-th (additional) iteration of BellmanFord(G, S) updates some dist-value.

Finding Negative Cycle

Algorithm:

• Run |V| iterations of Bellman–Ford algorithm, save node v relaxed on the last iteration
  
• v is reachable from a negative cycle
  
• Start from x ← v, follow the link x ← prev[x] for |V | times — will be definitely on the cycle
  
• Save y ← x and go x ← prev[x] until x = y again
  

2-6. Infinite Arbitrage

Detect Infinite Arbitrage

Lemma
It is possible to get any amount of currency u from currency S if and only if u is reachable from some node w for which dist[w] decreased on iteration V of Bellman-Ford.

Detect Infinite Arbitrage

• Do |V | iterations of Bellman–Ford, save all nodes relaxed on V -th iteration — set A
  
• Put all nodes from A in queue Q
  
• Do breadth-first search with queue Q and find all nodes reachable from A
  
• All those nodes and only those can have infinite arbitrage
  

Reconstruct Infinite Arbitrage

• During Breadth-First Search, remember the parent of each visited node
  
• Reconstruct the path to u from some node w relaxed on iteration V
  
• Go back from w to find negative cycle from which w is reachable
  
• Use this negative cycle to achieve infinite arbitrage from S to u