SSSP = Single Source Shortest Path

◈ Ford’s SSSP, the only SSSP algorithm

Relax tense edges until there are no more tense edges.

function FordSSSP(G: Graph, start: Vertex):
	InitSSSP(G, start)
	while there's at least 1 tense edge u→v in G:
		RelaxEdge(u→v)

The pseudocode above doesn’t really tell us how to check if there's at least 1 tense edge because it depends on the variant being implemented.

If there’s no solution (negative cycles), this function will run into an infinite loop because there will always be tense edges. The variants below handles this problem in different ways.

$\star$ Important Variants

All of the pages will use the notations and definitions in Shortest Paths: Definitions so be sure to check that out first.

SSSP

Lemmas & Proofs about SSSP

If an algorithm is a variant of Ford’s SSSP, then we can directly show its correctness by arguing that there are no more tense edges at the end of the algorithm.

This means that for all vertices $v$ in graph $G$, the path $\texttt{start}\leadsto v$ cannot be improved anymore.

Prof. Bai’s slides on SSSP Correctness

Lem. Max Non-negative SSSP Length

The shortest path between any 2 vertices is at most $V-1$ edges.

Otherwise we have negative cycles.

Lem. Bellman Ford Correctness

@Param $G:\texttt{\blue{Graph}}$

For every vertex $v\in G$ **and $i\in\Z_{\ge 0}$, after $i$ iterations of the repeat loop of BellmanFord(), we have:

$$ \ce{dist}[v]\le \ce{dist}_{\le i}[v] $$

Where $\ce{dist}_{\le i}$ denotes the state of the distance array after $i$ iterations