All Pairs Shortest Paths

Problema risolto con un algoritmo di programmazione dinamica.

Input: Grafo con $V=\{1,2,...,n\}$, funzione peso sugli archi $c:E\to R$ che non genera cicli negativi Output: cammini minimi tra ogni coppia di nodi di G

Si potrebbe trovare una soluzione utilizzando l’algoritmo di Bellman Ford per ogni vertice, ma verrebbe a costare troppo $O(|V{|}^2|E|)$.

Il sottoproblema si può definire tramite tre nodi $i,j,k$ di $V$, e $dist(i,j,k)=$ lunghezza del cammino minimo tra i e j che usa solo i nodi {1, 2, …, k}. Se il cammino minimo non esiste, dist() ritorna $+\infty$.

Algoritmo Floyd-Warshall

$$\min \begin{array}{c}\{\begin{array}{l}dist(i,j,k-1)\\ dist(i,k,k-1)+dist(k,j,k-1)\end{array}\end{array}$$

Il costo è di $O(n^3)$.

asd_41