Algoritmo di Bellman Ford

$O(|V||E|)$

Input: grafo $G=(V,E)$ senza cicli negativi funzione di costo non negativa sugli archi $c:E\to R^{+}$ nodo sorgente $s\in V$ Output: albero dei cammini minimi con radice $s$

L’algoritmo di Dijkstra, se ci sono archi con pesi negativi, non va più bene. Il mondo fermo non può esistere. Quindi nell’algoritmo di Bellman Ford si hanno solo la frontiera e il mondo lontano.

Bellman-Ford(G, c, s):
	for all u ∈ V do
		dist[u] := +∞
		prev[u] := 0
	dist[s] := 0

	for i = 1 to |V| - 1 do
		for all (u, v) ∈ E do
			if dist[v] > dist[u] + c(u, v) then
				dist[v] := dist[u] + c(u, v)
				prev[v] := u
	return prev[]

Costo computazionale $O(|V||E|)$

Per evitare di calcolare cicli negativi, si può implementare un controllo

Bellman-Ford(G, c, s):
	for all u ∈ V do
		dist[u] := +∞
		prev[u] := 0
	dist[s] := 0

	for i = 1 to |V| - 1 do
		for all (u, v) ∈ E do
			if dist[v] > dist[u] + c(u, v) then
				dist[v] := dist[u] + c(u, v)
				prev[v] := u

	for all (u, v) ∈ E do
		if dist[v] > dist[v] + c(u, v) then
			return "ciclo negativo"
	return prev[]

asd_33