Floyd Warshall

Algorytm Floyda-Warshalla oblicza najkrótszą drogę w grafie pomiędzy każda para wierzchołków w czasie O(n^3). Korzysta on z programowania dynamicznego, z nierówności trójkąta. Mając dane 3 wierzchołki u, v, k i chcąc obliczyć najkrótszą drogę miedzy u i v, skorzystamy ze wzoru odl[u, v]=min(odl[u, v], odl[u, k] + odl[k, v]). Algorytm testuje wiec tym wzorem wszystkie możliwe trójki wierzchołków (a jest ich n^3) i w ten sposób oblicza długość najkrótszej drogi miedzy każdą para wierzchołków w grafie. Podstawowa wersja algorytmu nie pozwala odtworzyć najkrótszej drogi a jedynie podaje jej długość, co jest dość istotną wadą. Można jednak temu zaradzić stosując tzw. macierz kierowania ruchem R[u][v]. Komórka R[u][v] przechowuje indeks wierzchołka pośredniego k przez który musimy przejść idąc optymalna droga u~>v. Wartości macierzy kierowania ruchem są aktualizowane w miarę przebiegu algorytmu. Potem, aby odtworzyć drogę u~>v należy użyć prostej funkcji rekurencyjnej, która korzysta z faktu ze drogi u->k i k->v mogą nie składać się z jednej krawędzi tylko z wielu, więc trzeba rozbić również je na u->k` i k`->k oraz k->k2` i k2`->v.

Przykładowy kod:

#include <iostream>
using namespace std;
int G[10000][10000]; //dlugosci krawedzi G[u][v];
int g[10000][10000]; //dlugosc najkrotszej sciezki u~>v
int R[10000][10000]; //macierz kierowania ruchem
const int INF=1000000001;
int N, M, u, v, w; //N-ilosc wierzcholkow; M-ilosc krawedzi
 
void init(){ //inicjuje graf i pozostale struktury wartosciami poczatkowymi
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            G[i][j]=INF;
            g[i][j]=INF;
            R[i][j]=-1;
        }
        G[i][i]=0;
        g[i][i]=0;
    }
}
 
void floyd(){ //znajduje najkrotsze sciezki miedzy kazda para wierzcholkow w grafie i wypelnia macierz kierowanie ruchem zeby mozna bylo odtworzyc przebieg kazdej drogi
    for(int k=0; k<N; k++){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(g[i][j]>g[i][k]+g[k][j]){ //jezeli droga z i do j, poprzez wierzcholek posredni k jest krotsza niz aktualnie najkrotsza znana trasa i->j to zaktualizuj
                    g[i][j]=g[i][k]+g[k][j];
                    R[i][j]=k; //oznacza to ze idac po sciezce i~>j trzeba przejsc przez k
                }
            }
        }
    }
}
 
void droga(int u, int v){ //odtwarza najkrotsza sciezke miedzy danymi wierzcholkami wykorzystujac macierz kierowania ruchem
    if(R[u][v]!=-1){ //dopoki nie dojdziemy do zwyklej krawedzi po ktorej trzeba wejsc to zchodz rekurencyjnie i wypisuj wierzcholek posredni k
        droga(u, R[u][v]);
        cout<<R[u][v]+1<<" ";
        droga(R[u][v], v);
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin>>N>>M;
    init();
    for(int i=0; i<M; i++){
        cin>>u>>v>>w;
        G[u-1][v-1]=g[u-1][v-1]=w;
        G[v-1][u-1]=g[v-1][u-1]=w; //zakladamy ze graf jest nieskierowany; w przypadku skierowanego usunac ta linijke
    }
    floyd();
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cout<<i+1<<"->"<<j+1<<" dl. "<<g[i][j]<<", przebieg: "<<i+1<<" ";
            droga(i, j);
            cout<<j+1<<endl;
        }
    }
    system("pause");
    return 0;
}
//Przykladowe wejscie:
/*10 17
1 2 13
1 9 33
2 3 27
2 4 1
2 10 8
2 9 9
3 4 10
4 10 11
4 6 2
4 5 3
5 6 9
6 10 666
6 7 66
7 8 333
7 9 33
9 10 3
6 9 15*/