Shortest-Path Algorithms

Bellman-Ford Algorithm

The Bellman–Ford algorithm finds shortest paths from a starting node to all nodes of the graph.

The upgrade of BF Algorithm is Dijkstra’s Algorithm.

• But it seems that there are good uses for bellman ford, because it works with negative weights while djikstra’s does not

Implementation

Code assumes that the graph is stored as an edge list edges that consists of tuples of the form $(a,b,w)$, edge from node $a$ to node $b$ with weight $w$.

for (int i = 1; i <= n; i++) distance[i] = INF;
distance[x] = 0;
for (int i = 1; i <= n-1; i++) {
	for (auto e : edges) {
		int a, b, w;
		tie(a, b, w) = e; // Unpack the tuple
		distance[b] = min(distance[b], distance[a]+w);
	}
}

Time complexity is $O(ne)$

Negative Edges

Bellman-Ford works with negative edge weights (but no negative cycles). This doesn’t work with Dijkstra’s Algorithm.

From CS341

Shortest Path Faster Algorithm (SPFA) Algorithm

The SPFA algorithm (”Shortest Path Faster Algorithm”) is a variant of the Bellman–Ford algorithm, that is often more efficient than the original algorithm.

Proof

Let ${\delta }_i(s,x)$ be the shortest path from $s$ to $x$ with at most $i$ edges.

If $\delta (s,u)\le d[u]$ and $\delta (s,v)\le d[v]$ before relaxation, then $\delta (s,v)\le d[v]$ post-relaxation.

Related

• Dijkstra’s Algorithm