2024-01-11 - APSP

universityin-classsubject-2101

2024-01-11

Algoritmi

APSP

Algoritmo di Floyd-Warshall

A differenza del metodo della moltiplicazione delle matrici, la dimensione non è più data dalla lunghezza del cammino, bensì dai nodi intermedi che possono essere coinvolti in un cammino minimo.
Per nodo intermedio si intende, dato un cammino, l’insieme dei nodi che non comprendono nodo iniziale e nodo finale.
Tale numero lo chiamiamo .

Sia l’insieme dei nodi del grafo.
Indicheremo con il sottoinsieme di che contiene i primi nodi di . Vale quindi
è definito per valori di da (insieme vuoto) a (quindi ).

Siano e rispettivamente i nodi di inizio e fine del cammino.
Valutando , deve esistere un cammino diretto che collega e .
Valutando , deve esistere un cammino diretto che collega e , oppure un nodo intermedio (il primo) che collega e .
Valutando , deve esistere un cammino diretto che collega e , oppure due nodi intermedi (i primi due) che collegano e .
…

Caso Base: .

Passo Induttivo
Si ottiene a partire da .

graph LR;
S((s))-- Vm-1 -->Vm((V_m))
S-- Vm -->T((t))
Vm-- Vm-1 -->T

Sia ( ha la stessa definizione della lezione precedente).

FLOYD-WARSHALL(w, n):
	D0 = w
	FOR m=1 TO n DO:
		Dm = new matrix[n x n]
		FOR i=1 TO n DO:
			FOR j=1 TO n DO:
				Dm[i, j] = Dm_1[i, j]
				IF Dm_1[i, m] + Dm_1[m, j] < Dm[i, j]
					Dm[i, j] = Dm_1[i, m] + Dm_1[m, j]

La complessità è .

In Bellman-Ford era possibile individuare eventuali cicli con peso negativo e restituire errore. Era sufficiente aggiungere un’ulteriore iterazione nel codice.
In Floyd-Warshall questo non è possibile. Bisogna assicurarsi che il grafo passato in input non contenga cicli con peso negativo.

L’implementazione precedente non salva in PI la cronologia dei nodi percorsi. Bisogna quindi modificare l’algoritmo.

FLOYD-WARSHALL(w, n):
	D0 = w
	FOR m=1 TO n DO:
		PIm = new matrix[n x n]
		Dm = new matrix[n x n]
		FOR i=1 TO n DO:
			FOR j=1 TO n DO:
				Dm[i, j] = Dm_1[i, j]
				PIm[i, j] = PIm_1[i, j]
				IF Dm_1[i, m] + Dm_1[m, j] < Dm[i, j]
					Dm[i, j] = Dm_1[i, m] + Dm_1[m, j]
					PIm[i, j] = PIm_1[m, j]

La seguente implementazione prevede l’utilizzo di un’unica matrice per D e `PI:

FLOYD-WARSHALL(w, n):
	D = w, PI = { ... (sistema di sopra)
	FOR m=1 TO n DO:
		FOR i=1 TO n DO:
			FOR j=1 TO n DO:
				IF D[i, m] + D[m, j] < D[i, j]
					D[i, j] = D[i, m] + D[m, j]
					PI[i, j]=PI[m, j]

vedi esempio nel libro

facendo gli esercizi “a mano”, se o contiene più infinito, l’intera riga o colonna può essere ricopiata direttamente