Znajdowanie najkrótszej drogi

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 :

1. Czy takie przedstawienie grafu jest odpowiednie i wygodnie się będzie tym posługiwać przy szukaniu najkrótszej ścieżki ?
2. 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 ?
3. 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.

1. Tak
2. Niech delete robi ten kto robi new. Na pewno nie tak jak to teraz zrobiłeś.
3. Jak nie umiesz dijkstry to napisz Bellmana Forda (2 pętle...) albo BFSa (jedna pętla plus kolejka)

2. No to w takim razie destruktor powinien znajdować się w klasie GrafMap, ale gdy napisze coś takiego :

        for(int i = 0 ; i < ListaMiast.size() ; i++)
            delete ListaMiast[i];

To za każdym razem będzie odwołanie do destruktora miasta. W klasie miasto natomiast jest lista wskaźników na krawędzie, które chyba też trzeba usuwać i jeśli tam też dam :

        for(int i = 0 ; i < ListaKrawedzi.size() ; i++)
            delete ListaKrawedzi[i];

To będzie odwołanie do destruktora klasy krawedz która posiada wskaźniki na miasta... I jeszcze w między czasie usuwając krawędzie początek w każdej liscie krawędzi jest taki sam ( krawędzie danego miasta zawsze posiadają to miasto ) więc będę usuwał usunięty już element. Troche to zaplątane i nie wiem jak sobie z tym poradzić.

To proste. Usuwając miasto powinieneś usuwać TYLKO to jedno miasto. Miasto nie jest "właścicielem" innych miast więc nie powinno ich ruszać.

No tak ale każde miasto ma swoje krawędzie ( wskazniki ) które chyba też trzeba usunąć. A z kolei krawędzi mają wskaźniki na miasta i jestem w pętli. Nie wiem czy jestem aż taki tępy ale jakoś nie moge znależć działającego rozwiązania.

Nie nie nie. Wskaźnik to wskaźnik, nic więcej! Nic usuwać nie trzeba! Usuwać trzeba tylko obiekty.
Wyobraź sobie że jest 10 kolegów i każdy z nich zna adres pozostałych. Jak jeden z nich się wyprowadza to tylko ON się wyprowadza, a jego koledzy nie. Normalnie warto byłoby żeby kazdy z pozostałych kolegów wyrzucił jego poprzedni adres, bo skoro się wyprowadził to jest już nieaktualny. Ale skoro wyprowadzają się wszyscy to jest to zbędne, bo po prostu nie wezmą ze sobą po wyprowadzce zeszytu z adresami i tyle.

U ciebie tak samo -> jak usuwasz miasto to usuwasz TYLKO to jedno miasto. To że to miasto ma informacje o pozostałych miastach nie ma żadnego znaczenia, bo to jest tylko adres.

Hmm wiec jesli w klasie grafMap mam vector wskaznikow na miasta to petla po nich i delete kazdego z nich zalatwi sprawe? Klasa krawedz i miasto nie potrzebuja destruktora ?

Skoro masz vector<krawedz*> (co uważam za rozwiązanie bez sensu...) to zapewne krawędzie też tworzysz przez new i musisz im zrobić delete kasując miasto. Ale oczywiście destruktor krawędzi ABSOLUTNIE nie ma robić delete na miastach na które krawędź wskazuje.
Nie widzę jednak powodu żebyś miał wektor wskaźników na krawędzie. Czemu nie wektor krawędzi po prostu? To by automatycznie rozwiązało problem.

Hmm no to jesli ten vector wskaznikow zamienie na wektor obiektow, zrobie delete kazdego wskaznika z vectora miast w klasie grafmap to zagwrantuje to zwolnienie calej przydzielonej pamieci ?

Jeśli krawędzi nie będziesz już tworzył przez "new" to tak. Bo zauważ że wtedy JEDYNE obiekty alokowane przez new to będą miasta, więc tylko miasta trzeba będzie zwolnić.

Jeżeli miasta wstawić do list<string> CityList; to nic nie trzeba zwalniać.
Może coś w tym stylu:

class GrafMap
  {
   class Node;
   class Edge
     {
      public:
      Node &to;
      double distance;
      Edge(Node &to,double distance):to(to),distance(distance) {}
     };
   class Node
     {
      public:
      list<Edge> Edges;
      string Id;
      Node(const string &Id):Id(Id) {}
     };
   public:
   list<Node> Nodes;
  };

Ok dzięki za pomoc , z reprezentacją już sobie poradziłem. Teraz czas na djikstre, tzn ten podstawowy algorytm działa, ale chciałbym go tak zmodyfikować aby wyznaczał on najkrótszą drogą pomiędzy miastami uwzględniając możliwość zmiany komunikacji tzn powiedzmy :
z miasta A do B można dojechać busem w 2h , samochodzem w 0.5h , pociagiem w 40min
z miasta B do C mozna dojechać busem w 1h . samochodem w 1.5h, pociagiem w 40min
z miasta C do D mozna dojechac busem w 0.5h , samochodem 1h , pociagiem 1h
I teraz powiedzmy urzystkownik ustala maksymalna ilosc zmian komunikacji przy
0 - pociag
1- pociag , pociag , bus
2- samochod , pociag , bus
Chyba dobrze policzyłem :P . Oczywiście miast będzie znaczniej więcej i nie zawsze wszystkie połączenia będą możliwe. Te czasy mam wczytane do klasy krawedz. Jesli "przejazdu" nie ma to czas wynosi 0. Czy można jakoś w miarę łatwo zmodyfikować djikstre ?

Każde miasto reprezentujesz przez trzy węzły (samochod , pociag , bus), podane krawędzie idą pomiędzy odpowiednimi węzłami.
Wewnątrz każdego miasta trzy węzły łączysz na początku drogami z kosztem 0.
Jeżeli po obliczeniu wyszło za dużo przesiadek to powiększasz koszt dróg pomiędzy każdą trójką reprezentującą miasto.
Metodą połowienia (bisekcji) szybko znajdziesz odpowiedni koszt (odpowiednią ilość przesiadek).

Średnio to rozumiem. Tzn zamiast przedstawiac krawedz jako obiekt ze skladowymi koniec, czaspociagu,czassamochodu , czasbusa zamienic go na 3 krawedze prowadzace do tego samego miasta ? Rozumiem ze trzeba by jeszcze zrobic jakies oznaczenie jaki to jest srodek komunikacji bo na koniec chcialbym wyswietlic czas i trasa wraz z wypisaniem srodka transportu. I co rozumiesz przez koszt wewnatrz miasta? Bo ja przyjmuje ze koszt przesiadki jest zerowy. Ograniczeniem jest tylko ilosc zmia podana przez uzytkownika.

Nie.
Abus -> Bbus = 2h; Asam -> Bsam = 0.5h; Apoc -> Bpoc = 40min (6 - węzłów, 3 krawędzi)
Do tego: Abus -> Asam = 0h; Asam -> Abus = 0h; Abus -> Apoc =0h; Apoc -> Abus =0h; Asam -> Apoc = 0h; Apoc -> Asam = 0h;
itd.

No ok czyli majac powiedzmy 2 srodki transportu tworzylbym 2 takie same obiekty typu miasto z dodatkowym polem bool ktore okreslaloby ten srodek( false - samochod. true - pociag) nastepnie w algorytmie djikstry jesli nastepowalaby zmiana z false na true zwiekszalbym licznik przesiadek. Dobrze rozumiem ? Tylko teraz jak ta ilosc ograniczyc? Co da mi zwiekszenie kosztow pomiedzy srodkami transportu ( ja chce zeby ona byla zerowa) ? I jak rozumiem po kazdym takim zwiekszeniu musialbym algorytm djikstry zapuszczac jeszcze raz tak ?

Nie.

1. Każde miasto przedstawione jako trzy węzły połączone pomiędzy sobą sześcioma krawędziami o koszcie 0 - na początek.
2. Obliczasz dla takiego stanu najkrótszą drogę jeżeli wyszło ci zero przesiadek to koniec obliczeń (masz wynik)
3. Sumujesz wszystkie koszty w grafie i wstawiasz je w te wewnątrzmiastowe krawędzie (w każdą), jeżeli wyszło przesiadek więcej niż zadano to koniec obliczeń (nie da się tego dokonać)
4. Metodą połowienia znajdujesz optymalny układ.

Kurde, dalej nie moge sobie tego wyobrazić. Od początku ... Sama reprezentacja grafu i potem zliczanie przesiadek którą napisałem wcześniej tzn :
No ok czyli majac powiedzmy 2 srodki transportu tworzylbym 2 takie same obiekty typu miasto z dodatkowym polem bool ktore okreslaloby ten srodek( false - samochod. true - pociag) nastepnie w algorytmie djikstry jesli nastepowalaby zmiana z false na true zwiekszalbym licznik przesiadek. Dobrze rozumiem ?

• stworzenie między dwoma obiektami reprezentujacymi to samo miasto 2 krawędzi ( w jedną i drugą stronę o wadze 0 ) , trzymanie ich(miast) jako vector w klasie graf + kazde miasto posiadałoby vector krawędzi jakie się z nim łączą. Czy sama reprezentacja byłaby dobra ?
  A co do tego algorytmu mógłbyś podać jakiś przykład , szczególnie pkt 3-4.

Powiedz którego słowa nie rozumiesz.

1. Chciałbym wiedzieć czy takie przetrzymywanie(z boolem- w przypadku 2 miast) grafu będzie odpowiednie oraz czy zliczanie przesiadek ( poprzez sprawdzanie zmian false-> true i odwrotnie ) jest dobrym pomysłem ?
2. Sumujesz wszystkie koszty w grafie i wstawiasz je w te wewnątrzmiastowe krawędzie (w każdą), jeżeli wyszło przesiadek więcej niż zadano to koniec obliczeń (nie da się tego dokonać)
Metodą połowienia znajdujesz optymalny układ.

Tego w ogóle nie rozumiem. Z algorytmu wyjdzie mi np. droga 3h z 3 przesiadkami a uzytkownik podał, że maksymalnie mogą być 2. I co mam z tym dalej zrobić ? 
Te 3h wstawić w każdą krawędź łącząca te same miasta? Co to spowoduje ?

Ad 1. Nie widzę tego algorytmu - chyba że chodzi cię o brutal force (który jest dobry tylko wtedy kiedy nie ma innego algorytmu).
Ad 2. Spytałem: - "którego słowa nie rozumiesz" a nie: - "w którym zdaniu jakiegoś słowa nie rozumiesz" - widzisz różnicę?

1. Sumujesz wszystkie koszty w grafie
2. Wstawiasz wyliczoną wyżej sumę w te wewnątrzmiastowe krawędzie (w każdą z krawędzi, tą samą gigantyczną liczbę)
3. Liczysz dijkstrą
4. Jeżeli wynik ma więcej przesiadek niż zadał użytkownik, to poinformuj użytkownika że nie da się tego dokonać.

Ad. 1 No to w takim razie jak moglbym sprawdzac czy przesiadka nastapila czy nie? I jak je oznaczyc zeby mozna bylo stwierdzic czy "dojechalismy" busem czy samochodem. Ad. 2 Sorry ale jakos ciezko mi przychodzi ogarniecie tego. Czyli djikstre maksymalnie liczymy2 razy tak ?

Ad 1. Normalnie zliczasz z trasy, algorytm Dijkstry pozwala zachować ścieżkę.
Dijkstry liczymy wielokrotnie na każdym kroku algorytmu bisekcji.

To znów ja :P Ostatnio dałem sobie spokój z tym zadaniem, ale postanowiłem do niego wrócić. @_13th_Dragon mam nadzieje, że twoja cierpliwość do mnie jeszcze się nie skończyła. Przeczytałem jeszcze raz twoje wszystkie wypowiedzi i nie moge zrozumieć twojego pomysłu na ten problem. Reprezentując graf tak jak podpowiedziałeś ( 1 miasto - 2 obiekty(przy 2 srodkach transportu)oraz ustawienie początkowe kosztów między nimi na 0) licze Dijkstre, dostaje jakąś droge i okazuje się, że liczba zmian transportu jest zbyt duza. Wstawiam sumę wszystkich krawędzi w grafie do tych między obiektami reprezentującymi to samo miasto i jeśli z tego znów wyjdzie liczba zmian ( z tego co zrozumiałem w tym przypadku przesiadki nie będą się opłacać w ogóle ) większa od podanej przez użytkownika to nie da się tego osiągnąć. No dobra ale jak rozumiem są to 2 skrajne przypadki a co pomiędzy? Metoda bisekcji ... ale co ja mam za jej pomocą zmieniać / szukać ? Co więcej jeśli algorytm ten polega na zwiększaniu kosztów zmian transportu a ja chce by wynosiły one 0 , to po policzeniu Djikstry najkrótsza droga będzie zwiększona o te koszty. Jak sobie z tym poradzić ?

Użytkownik mówi że może być 5 - przesiadek
Dla kosztu przesiadki =0 wychodzi 30 przesiadek
Dla kosztu przesiadki =S wychodzi 2 przesiadki
Liczymy dla kosztu przesiadki =ŚRODEK=(0+S)/2 powinno wyjść coś pomiędzy 2 a 30 przesiadek.
Więc znajdujesz taką liczbę ŚRODEK dla której:
Dla kosztu przesiadki =ŚRODEK wychodzi 5 przesiadek (to akurat ta szuana trasa)
Dla kosztu przesiadki =ŚRODEK+1 wychodzi 4 przesiadki

Ok o dziwo wyglada na to ze pojalem to wiec zabieram sie do pisania. Dzieki chociaz wydaje mi sie ze jeszcze tu wroce : P.aha i jeszcze jedno S to zawsze suma po wszystkich kosztach krawedzi czy najktrotsza znaleziona aktualnnie trasa ?

Na początku 0 i S to min i max dalej metoda klasyczna połowienia.

No wiec nie obeszło się bez problemów... Na początku moje dodawanie przy nie istniejących obu punktach krawędzi :

            przystanek* pocz = new przystanek(nazwapo,true);
            przystanek* pocz2 = new miasto(nazwapo,false);
            ListaMiast.push_back(pocz);
            ListaMiast.push_back(pocz2);
            krawedz krAB(pocz2,0);
            krawedz krBA(pocz,0);
            pocz->ListaKrawedzi.push_back(krAB);
            pocz2->ListaKrawedzi.push_back(krBA);
            miasto* kon = new miasto(nazwako,true);
            miasto* kon2 = new miasto(nazwako,false);
            ListaMiast.push_back(kon);
            ListaMiast.push_back(kon2);
            krawedz krkAB(kon2,0);
            krawedz krkBA(kon,0);
            kon->ListaKrawedzi.push_back(krkAB);
            kon2->ListaKrawedzi.push_back(krkBA);
            krawedz krA(kon, samo );
            krawedz krB(kon2, autob);
            pocz->ListaKrawedzi.push_back(krA);
            pocz2->ListaKrawedzi.push_back(krB);

Jako false / true chciałem oznaczyc czy jest to przystanek autobusowy czy "samochodowy", żeby móc sprawdzać ilość przesiadek.

1. Czy takie dodawanie krawedzi jest ok ? ( tzn jest to jeden z 4 if'ów, najbardziej rozbudowany bo oba konce nie istnieją ).
2. Którą wersje miasta mam wybrać jako początkowe miasto w djikstrze? Przy bardzo dużym koszcie przesiadki i wybraniu jednego może okazać się, że krótsza droga była tym drugim środkiem transportu?
3. Jak w szybki sposób zmieniać koszt w węzłach wewnątrz miast ?
   na razie chyba tyle pytań. Pozdrawiam i dzięki za dotyczasową pomoc.

Z powyższymi problemami już sobie poradziłem ale zatrzymałem się na warunku w pętli metody bisekcji. Jaki warunek musi być, zeby znaleŹć tą najkrótszą ścieżkę biorąc pod uwage ograniczenie w postaci zmian środka transportu?To że dla kosztu = srednia , liczbazmian == liczbie podanej przez uzytkownika , a dla kosztu=srednia + 1, liczbazmian =( liczbie podanej przez uzytkownika -1 ) nie działa tzn dostaje zawsze 0 przesiadek pomimo, że są one opłacalne i ograniczenie narzucone przez użytkownika na to pozwala. W samej dijkstrze przy zwiekszaniu / zmniejszaniu kosztow zmian, raczej błędu nie ma bo dla zerowych kosztów wykonywanych jest maksymalnie dużo przesiadek do skrócenia drogi natomiast przy koszcie równym sumie wszystkich krawedzi zero przesiadek. Chodzi mi tylko o warunek kóncowy w algorytmie bisekcji. Proszę o pomoc i pozdrawiam.

No właśnie napisałeś :

Więc znajdujesz taką liczbę ŚRODEK dla której:
Dla kosztu przesiadki =ŚRODEK wychodzi 5 przesiadek (to akurat ta szuana trasa)
Dla kosztu przesiadki =ŚRODEK+1 wychodzi 4 przesiadki

ale nie działa. Tzn dla niektórych przypadków działa ale czasem program się zapętla bo nie może znaleŹć takiego środka, a rozwiązanie istnieje.