# Dijkstra Algorithm

###### tags: `MIT` `面試準備`

### Notaion

$d[v]:$ length of the current sortest path from s to v
$\delta[s, v]:$ shortest path from s to v
$\Pi[v]:$ predecessor of v

### Relaxing Step

Relax(u,v,w):
if(d[v]>d[u]+w(u,v))
    d[v]=d[u]+w[u,v]
    Pi[v] = u;

:::success
Lemma: The relaxation operation maintains the invariant that $d[v]\geq\delta[v]$ for all vertices.
:::

Proof: By induction on the number of steps.
By induction, $d[u]\geq\delta[s,u]$.
By triangle inequality, $\delta[s,v]\leq\delta[s,u]+\delta[u,v]$.

$\delta[s,v]\leq d[u]+w(u,v)=d(u)$

- 注意這邊用三角不等式是用 $\delta[s,v]$ 而不是 single edge weight ，因此是可以符合的。

### DAG (Direct Acyclic Graph)


1. Topological sort th DAG.
Path from to u to v implies that u is before v in the ordering.
2. One pass over vertices in topologically sorted order relaxing each edge that leaves each vertex.

Time Complexity: $O(E+V)$

### Dijkstra


Dijkstra(G, w, s):
    Initialize (G, s); //d[s]=0
    Set S = null, Q = all vertices;
    while(Q!=empty) {
        u = min(Q); //delete u from Q
        S = S.push(u);
        for each vertex v in Adj[u] {
            Relax(u, v, w);
        }
    }

- 其中 Q 通常用 priority queue 去 implement，而他比較的值便是 $d[v]$