Dat je usmeren težinski graf sa \(n\) čvorova. U ovom grafu između svaka dva čvora postoji po jedna usmerena grana u oba smera. Nad takvim grafom igramo sledeću igru:
Sa standardnog ulaza se prvo učitava broj čvorova \(n\) (1 <= n <= 500), a zatim i matrica povezanosti dimenzija \(n*n\), gde je element \(a_{ij}\) usmerena grana od čvora \(i\) do čvora \(j\). Najzad, unosi se \(n\) čvorova u redosledu kojim se uklanjaju.
Na standardni izlaz ispisati redom rezultate zbira svih najkraćih puteva pre svakog koraka, razdvojene razmakom.
2 0 5 4 0 1 2
9 0
4 0 3 1 1 6 0 400 1 2 4 0 1 1 1 1 0 4 1 2 3
17 23 404 0
Naivno rešnjenje problema bi podrazumevalo pokretanje Flojd-Varšalovog algoritma pre svakog uklanjanja čvora, a zatim i računanje sume svih najkraćih puteva. Kako Flojd-Varšalov algoritam ima složenost \(O(|V|^3)\), ukupna složenost ovog pristupa bila bi \(O(|V|^4)\).
Bolju složenost možemo dobiti posmatrajući problem uklanjanja čvorova kao problem dodavanja čvorova u obrnutom redosledu. Naime, ako obrnemo vektor čvorova koje uklanjamo i pokrenemo Flojd-Varšalov algoritam tako da “središnji” čvor iz algoritma redom uzima vrednosti iz ovog vektora, postižemo efekat da se u \(i\)-tom koraku računaju samo najkraći putevi preko čvorova koji su preostali do \((n-i)\)-tog trenutka. Možemo u svakom koraku direktno ažurirati matricu suseda, ali pri ispisu moramo voditi računa da su oba čvora čiji najkraći put uračunavamo u sumu do tog trenutka već bili “središnji”
Složenost ovog pristupa je \(O(|V|^3)\), jer pokrećemo samo jednu instancu Flojd-Varšalovog algoritma.
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <tuple>
#include <algorithm>
using namespace std;
class Graph {
private:
int broj_cvorova;
vector<vector<int>> matrica_suseda;
public:
Graph(int broj_cvorova) {
this->broj_cvorova = broj_cvorova;
matrica_suseda.resize(broj_cvorova);
for(int i = 0; i < broj_cvorova; i++)
matrica_suseda[i].resize(broj_cvorova);
}
void dodaj_granu(int u, int v, int weight) {
matrica_suseda[u][v] = weight;
}
void floyd_warshall(vector<int> &poredak_uklanjanja) {
reverse(poredak_uklanjanja.begin(), poredak_uklanjanja.end());
vector<bool> aktivan(broj_cvorova);
fill(aktivan.begin(), aktivan.end(), false);
vector<int> resenje(broj_cvorova);
for(int i = 0; i < broj_cvorova; i++){
int novi = poredak_uklanjanja[i];
aktivan[novi] = true;
for(int j = 0; j < broj_cvorova; j++){
for(int k = 0; k < broj_cvorova; k++){
matrica_suseda[j][k] = min(matrica_suseda[j][k],
matrica_suseda[j][novi]+matrica_suseda[novi][k]);
}
}
int suma = 0;
for(int j = 0; j < broj_cvorova; j++){
if(!aktivan[j]) continue;
for(int k = 0; k < broj_cvorova; k++){
if(!aktivan[k]) continue;
suma += matrica_suseda[j][k];
}
}
resenje.push_back(suma);
}
reverse(resenje.begin(), resenje.end());
for(int i = 0 ; i < broj_cvorova; i++){
cout << resenje[i] << " ";
}
cout << "\n";
}
};
int main() {
int n;
cin>>n;
Graph *G = new Graph(n);
int w;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin >> w;
G->dodaj_granu(i, j, w);
}
}
vector<int> poredak_uklanjanja(n);
for(int i=0;i<n;i++){
cin>>poredak_uklanjanja[i];
poredak_uklanjanja[i]--;
}
G->floyd_warshall(poredak_uklanjanja);
delete G;
return 0;
}