Bellman-Ford Algorithm is a dynamic programming problem that solves single-source shortest path.

d[v] = \infty
d[s] = 0
for i = 0, ..., n-2:
    for v in v:
        d_prev = d
        for u in v.in_neigbors:
            d[v] = min(d_prev[v], d_prev[u] + w(u,v))

Notice you need \(O\qty(n)\) space (2 \(d\) rounds, the previous round and the next round), and runtime is \(O\qty(nm)\) (outer \(n\) loop, inner is an iteration between \(deg\qty(v)*|v| = |e| = m\); that is, we have an minimum over the degree of each \(v\) for every \(v\), which adds up to the total number of edges.)

constituents

• a weighted directed graph, meaning edges have weights
• where cost of a path is the sum of the weights along that path
• the shortest path is the path with the minimum cost
• starting node \(s\), target node \(t\)

Each node has two states:

• unlabeled
• labeled

And stores a piece of information:

\(d\qty(v) = \text{distance}\qty(s, v)\)

We initialize \(d\qty(v) = \infty, v \neq s\) , and \(d\qty(s) = 0\).

requirements

1. pick the node \(u\) that has unlabeled state with smallest \(d\qty(u)\)
2. for all neighbor v of u:
   1. set \(d\qty(v) = \min \qty(d\qty(v), d\qty(u) + \text{edgeWeight}\qty(u,v))\)
3. mark \(v\) as labeled

def dike(G,s,t):
    set verticies to State.NOTSURE
    for v in G.V:
        d[v] = float("+inf")
        p[v] = None # (for parents)
    d[s] = 0
    while State.NOTSURE in G.V:
        # get node with minimum distance that's not sure
        u = argmin(d[v] for v in G.V if v.state == State.NOTSURE)
        u.state = State.SURE
        for v in u.out_neighbors:
            d[v] = min(d[v], d[u] + edgeWeight(u,v))
            if d[v] was changed:
               p[v] = u # (for obtaining next path in chain for shortes paths)
    return d[t]

additional information

proof

Let’s start with a lemma

Floyd-Warshall Algorithm solves the all-pairs shortest paths problem. We solve using dynamic programming.

constituents

initialization: d[u,v] = ∞ if u and v are not neighbors; d[u,v] = w(u,v) if u and v are neighbors; d[u,u] = 0.

subproblem: for all pairs \(u,v\), find the cost of the shortest path from \(u\) to \(v\) so that we only use the first \(1 … k-1\) vertices as internal “hops”.

recursion: two cases; for the \(k\) th new vertex introduced, if the shortest path does not go through \(k\) even with \(k\) added, then we can just copy the previous shortest path; if the shortest path goes through \(k\):

The Huffman Coding scheme is a coding scheme which gives the best Prefix-Free code (with the smallest Average Codeword Length) for any source with any arbitrary distribution.

Huffman Coding is Bounded

the Huffman Coding has the property that:

\begin{equation} \bar{l} \leq H(x) +1 \end{equation}

So, recall that any prefix free code for a source has at least entropy length; this gives:

\begin{equation} H(x) \leq \bar{\ell} \leq H(x)+1 \end{equation}

for source \(X\), and entropy of \(X\) given by \(H(X)\), and a Average Codeword Length returned by Huffman Coding \(\bar{\ell}\).