Mam pewien problem z implementacją algorytmu który będzie znajdował najkrótsze ścieżki w grafie ze źródła do pozostałych wierzchołków. Zaimplementowałem algorytm który liczy mi długość ścieżek od punktu 0 do pozostałych . Jak dodać dodatkową tablice aby zapamiętywała najkrótsze ścieżki od punktu 0 do pozostałych .
class Graf
{
struct krawedz{
int wierzcholek;
};
int V;
vector< krawedz > *sasiedzi;
public:
Graf(int V){
this->V = V;
sasiedzi = new vector<krawedz>[V];
}
void Dodaj_krawedz(int u, int v){
sasiedzi[u].push_back({v});
}
void Najkrotsza_sciezka(){
priority_queue<int> priority_q;
//vector dla dystansów
vector<int> odleglosc(V, nieskonczonosc);
priority_q.push(0);
odleglosc[0] = 0;
while (!priority_q.empty())
{
int u = priority_q.top();
priority_q.pop();
for (auto i = sasiedzi[u].begin(); i != sasiedzi[u].end(); ++i)
{
int v = (*i).wierzcholek;
//jesli istnieje krotsza sciezka
if (odleglosc[v]==nieskonczonosc)
{
odleglosc[v] =odleglosc[u] + 1;
priority_q.push(v);
}
}
}
for(int i=0; i<V;i++){
cout<< odleglosc[i]<<endl;
}
}
};
Podpowiedź do zadania