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