akueisara/1. Fastest Route.md

## 1. Fastest Route.md

      
    Raw
  

              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

      
    Raw
  

              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