Algorytm Floyda-Warshalla

Algorytm Floyda Warshalla wyznaczający najmniejszy koszt przejścia między każdą parą wierzchołków.

• Złożoność czasowa wynosi O(n³),
• złożoność pamięciowa wynosi O(n²),
• graf może posiadać krawędzie o ujemnych wagach, ale nie może posiadać ujemnych cykli,
• algorytm wykorzystuje technikę programowania dynamicznego.

Wyznacz najmniejsze koszty przejścia dla każdej pary wierzchołków.

Wejście

W pierwszym wierszu wprowadzamy dwie liczby naturalne V i E określające odpowiednio liczbę wierzchołków oraz liczbę połączeń w grafie. W kolejnych E wierszach po trzy liczby definiujące połączenie między wierzchołkiem o numerze a oraz wierzchołkiem o numerze b o wadze w, 0 < a ≠ b ≤ n, |w| < 100, graf nie posiada ujemnych cykli.

Wyjście

Pary wszystkich wierzchołków a i b oraz najmniejszy koszt przejść między nimi.

//algorytm.edu.pl
//algorytm Floyda Warshalla do wyznaczania najkrótszych ścieżek 
//między każdą parą wierzchołków grafu.
//Nie mogą występować ujemne cykle
#include<bits/stdc++.h>
using namespace std;
vector <vector <long long> > tab;

//wyznaczenie najkrótszych ścieżek między każdą parą wierzchoków w czasie V^3
void Floyd_Warshall()
{
	for(int i = 1;i<tab.size();i++)
		for(int j=1;j<tab.size();j++)
			for(int k=1;k<tab.size();k++)
				if(tab[j][k] > tab[j][i] + tab[i][k])
					tab[j][k] = tab[j][i] + tab[i][k];
}

int main()
{
	int V, E; //wierzchołki i krawędzie
	cin>>V>>E;
	
	tab.resize(V+1); //utworzenie V + 1 wierszy (chcemy mieć dostęp do wierza o indeksie V)
	for(int i=1;i<=V;i++) 
		tab[i].resize(V+1, INT_MAX); //utworzenie V + 1 elementów w każdym wierszu i ustawienie na 
		//"nieskończoność" czyli INT_MAX — największą wartość mieszczącą się w zmiennej typu int
	for(int i=1;i<=V;i++)
		tab[i][i] = 0; //odległość od i-tego wierzchołka do siebie samego jest równa 0
		
	//wczytanie krawędzi i ich wag
	int a, b, w;
	while(E--)
	{
		cin>>a>>b>>w; //krawęd a -> b o wadze w
		tab[a][b] = w;
	}
	//po wykonaniu tego algorytmu w komórce tab[i][j] przechowujemy 
	//najmniejszy koszt przejścia z wierzchołka i do wierzchołka j
	Floyd_Warshall(); 
	//wypisujemy wyznaczone koszty
	for(int i = 1; i<= V; i++)
		for(int j = 1; j<=V; j++)
			if(tab[i][j] == INT_MAX)
				cout<<"brak połączenia\n";
			else
				cout<<i<<" -> "<<j<<": "<<tab[i][j]<<endl;
	return 0;
}

Przykład:

Wejście:

3 3
1 2 2
2 3 4
3 1 2

Wyjście:

1 -> 1: 0
1 -> 2: 2
1 -> 3: 6
2 -> 1: 6
2 -> 2: 0
2 -> 3: 4
3 -> 1: 2
3 -> 2: 4
3 -> 3: 0