Witam. Musze zaimplementować w c++ i napisać funkcje znadującą najkrótszą ścieżkę między dwoma dowolnymi wierzchołkami. Wierzchołkami są nazwy miast , krawędzie mają ustaloną wagę. Graf skierowany. na razie mam coś takiego :
class miasto;
class krawedz
{
public:
miasto *pocz;
miasto *kon;
unsigned odleglosc;
public:
krawedz(miasto *first, miasto *last, unsigned droga) :
pocz(first) , kon(last) , odleglosc(droga) {};
~krawedz()
{
if(pocz != NULL ) {delete pocz; pocz = NULL;}
}
};
class miasto
{
public:
string nazwa;
vector<krawedz*> ListaKrawedzi;
miasto(string id): nazwa(id) {};
~miasto()
{
}
};
class GrafMap
{
public:
vector<miasto*> ListaMiast;
~GrafMap();
int szukajMiasta(const string& szukany)
{
for(int i= 0 ; i < ListaMiast.size() ; i++)
if(ListaMiast[i]->nazwa == szukany) return i;
return -1;
}
void dodajKrawedz(string nazwapo, string nazwako , unsigned dlugosc)
{
int szukajpocz =szukajMiasta(nazwapo);
int szukajkon =szukajMiasta(nazwako);
if(szukajpocz == -1 && szukajkon != -1)
{
miasto* pocz = new miasto(nazwapo);
ListaMiast.push_back(pocz);
krawedz *kr = new krawedz(pocz, ListaMiast[szukajkon], dlugosc);
pocz->ListaKrawedzi.push_back(kr);
}
if(szukajpocz == -1 && szukajkon == -1)
{
miasto* pocz = new miasto(nazwapo);
ListaMiast.push_back(pocz);
miasto* kon = new miasto(nazwako);
ListaMiast.push_back(kon);
krawedz *kr = new krawedz(pocz, kon, dlugosc);
pocz->ListaKrawedzi.push_back(kr);
}
if(szukajpocz != -1 && szukajkon != -1)
{
krawedz *kr = new krawedz(ListaMiast[szukajpocz], ListaMiast[szukajkon], dlugosc);
ListaMiast[szukajpocz]->ListaKrawedzi.push_back(kr);
}
if(szukajpocz != -1 && szukajkon == -1 )
{
miasto* kon = new miasto(nazwako);
ListaMiast.push_back(kon);
krawedz* kr = new krawedz(ListaMiast[szukajpocz], kon, dlugosc);
ListaMiast[szukajpocz]->ListaKrawedzi.push_back(kr);
}
}
I tu pojawiają się moje pytania :
- Czy takie przedstawienie grafu jest odpowiednie i wygodnie się będzie tym posługiwać przy szukaniu najkrótszej ścieżki ?
- Ponieważ klasa miasto zawiera listę wskaźników na krawędzie , a każda krawędź zawiera wskaźniki na miasta to jak napisać do nich destruktory ?
- Czy mógłby mi ktoś przybliżyć implementację tego algorytmu? Tzn wiem, że to Dijkstra ale jakoś nie mogę sobie tego wyobrazić w c++.
Proszę o pomoc. Pozdrawiam.