OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie
Problem najkrótszych ścieżek między wszystkimi parami wierzchołków
można rozwiązać wykonując n razy algorytm dla problemu najkrótszych
ścieżek z jednym źródłem.
W przypadku nieujemnych wag krawędzi można zastosować algorytm Dijkstry.
Złożoność obliczeniowa będzie typowo O(n^3) dla macierzy sąsiedztwa
i O(n m log n) dla listy sąsiedztwa.
W przypadku ujemnych wag musimy użyć algorytm Bellmana-Forda,
co daje złożoność O(n^2 m) [O(n^4) dla grafów gęstych].
Istnieją specjalne algorytmy dostosowane do problemu najkrótszych
ścieżek między wszystkimi parami wierzchołków.
Na ogół te algorytmy zakładają reprezentację grafu w postaci macierzy
sąsiedztwa.
Na wejściu algorytmu jest dana macierz Weight[] wymiaru n × n
reprezentująca wagi krawędzi grafu skierowanego ważonego G.
Weight[i,j] = 0 dla i = j,
Weight[i,j] = w(i,j) dla (i,j) ∈ E(G),
Weight[i,j] = +∞ dla i ≠ j oraz (i,j) ∉ E(G).
Wynikiem działania algorytmów jest macierz D[] wymiaru n × n, gdzie D[i,j] jest wagą najkrótszej ścieżki z wierzchołka i do wierzchołka j.
Najkrótsze ścieżki będą reprezentowane przez macierz poprzedników Parent[] wymiaru n × n. Parent[i,j] jest poprzednikiem j na pewnej najkrótszej ścieżce z i do j. Parent[i,:] reprezentuje podgraf poprzedników dla wierzchołka i.
Jest to algorytm programowania dynamicznego, w którym w pętli głównej programu wykonywane są operacje podobne do mnożenia macierzy. Wykorzystuje się lemat, że wszystkie podścieżki każdej najkrótszej ścieżki są najkrótszymi ścieżkami. Wagi najkrótszych ścieżek oblicza się metodą wstępującą.
Oznaczenie: L[i,j]^{(m)} jest to najmniejsza waga ścieżki
z wierzchołka i do wierzchołka j spośród tych, które zawierają
co najwyżej m krawędzi.
L[i,j]^{(0)} = 0 dla i = j,
L[i,j]^{(0)} = +∞ dla i ≠ j,
L[i,j]^{(m)} = min_k{ L[i,k]^{(m-1)} + Weight[k,j] } dla m > 0.
Algorithm ExtendedShortestPaths(L,Weight): # total O(n^3) time
let M be a new matrix n × n
for i from 1 to n do
for j from 1 to n do
set M[i,j] to infinity
for k from 1 to n do
set M[i,j] to min{M[i,j], L[i,k] + Weight[k,j]}
return M
Input: A weight matrix (Weight).
Output: Distances (Distance).
Algorithm SlowAllPairsShortestPaths(Weight): # total O(n^4) time
set L^{(1)} to Weight
for m from 2 to n-1 do
let L^{(m)} be a new matrix n × n
set L^{(m)} to ExtendedShortestPaths(L^{(m-1)},Weight)
# Check for negative-weight cycles.
for i from 1 to n do
if L[i,i]^{(m)} < 0 then
return error "negative cycle detected"
return L^{(n-1)} # Distance
# Modyfikując procedury SlowAllPairsShortestPaths i ExtendedShortestPaths
# można jednocześnie z L obliczyć macierz poprzedników (Parent).
Input: A weight matrix (Weight).
Output: Distances (Distance).
Algorithm FasterAllPairsShortestPaths(Weight): # total O(n^3 log n) time
set L^{(1)} to Weight
set m to 1
while m < n-1 do
let L^{(2m)} be a new matrix n × n
set L^{(2m)} to ExtendedShortestPaths(L^{(m)},L^{(m)})
set m to 2m
# Check for negative-weight cycles.
for i from 1 to n do
if L[i,i]^{(m)} < 0 then
return error "negative cycle detected"
return L^{(m)} # Distance
Algorytm Floyda-Warshalla również stosuje programowanie dynamiczne.
Bierze się pod uwagę wewnętrzne wierzchołki najkrótszej ścieżki.
Niech D[i,j]^{(k)} będzie wagą najkrótszej ścieżki z wierzchołka i
do wierzchołka j, której wszystkie wewnętrzne wierzchołki należą
do zbioru {1,2,...,k}.
D[i,j]^{(0)} = Weight[i,j],
D[i,j]^{(k)} = min{D[i,j]^{(k-1)},
D[i,k]^{(k-1)} + D[k,j]^{(k-1)}} dla k > 0.
Poszukiwanym rozwiązaniem jest macierz D^{(n)}.
Input: A weight matrix (Weight).
Output: Distances (Distance).
Algorithm FloydWarshall(Weight): # total O(n^3) time
set D^{(0)} to Weight
for k from 1 to n do
let D^{(k)} be a new matrix n × n
for i from 1 to n do
for j from 1 to n do
D[i,j]^{(k)} = min{D[i,j]^{(k-1)}, D[i,k]^{(k-1)} + D[k,j]^{(k-1)}}
# Check for negative-weight cycles.
for i from 1 to n do
if D[i,i]^{(n)} < 0 then
return error "negative cycle detected"
return D^{(n)} # Distance
# Algorytm Floyda-Warshalla działa poprawnie, kiedy w macierzach D^{(k)}
# opuścimy górne indeksy i będziemy używać jednej macierzy D.
# Wtedy złożoność pamięciowa zmniejsza się z O(n^3) do O(n^2).
#
# Jednocześnie z obliczaniem macierzy D można obliczać macierz poprzedników (Parent).
Zaimplementować algorytm mnożenia macierzy do znajdowania najkrótszych ścieżek między wszystkimi parami wierzchołków. Wygenerować przykładowy graf skierowany ważony z n=10. Wyznaczyć najkrótsze ścieżki pomiędzy wierzchołkami.
Zaimplementować algorytm Floyda-Warshala znajdowania najkrótszych ścieżek między wszystkimi parami wierzchołków Wygenerować przykładowy graf skierowany ważony z n=10. Wyznaczyć najkrótsze ścieżki pomiędzy wierzchołkami.