algorytm Dijkstry- problemu początkującego

0

Cześć, potrzebuję pomocy przy implementacji algorytmu dijkstry na przykładowym grafie. Stowrzylam sobie taki graf( w załączniku) No i wedlug mnie najkrótsza droga będzie szla p--> c--> e-->k. Nie bardzo wiem tylko czy według mojego rozumowania ten algorytm będzie działał.
etapy moich rozważań:
1.wierzcholek startowy p. Rozwazamy najkrótszą ścieżkę wśród sąsiadów a i c. Wybieram c. Dodaję wierzchołek startowy i c do zbioru wierzchołków odwiedzonych
2. znowu rozwazam sasiadow i wybieram e.
3. sprawdzam sąsiadów e i sprawdzam zależności między sąsiadami i odkrywam, że droga do A wynosi juz nie 10 tylko 6. dodaję e do odwiedzonych
4. docieram do wierzcholka koncowego k. dodaję k do odwiedzonych

No i mam problem, ponieważ algorytm będzie działał dopóki zbiór wierzchołków nieodwiedzonych nie będzie pusty. Czy mam uważać, że wierzchołki, które byly po prostu przeglądane są odwiedzone? Wiem, że to banalne pytanie, ale uczę się dopiero :)

0

Algorytm możesz przerwać wcześniej jeśli znalazłeś wierzchołek końcowy. Zaznaczone w kodzie niżej jako "then exit". To jest zwykle około 70% wszystkich wierzchołków. Wyjaśnienie tu.

Algorytm "A star", przeszukuje o wiele mniej, choć rozwiązanie może być nieco gorsze od optymalnego i często ciężko jest zdefiniować funkcję heurystyczną "odległości wierzchołków". W algorytmie Dijkstry będziesz miał ogromną trudność zaimplementowania kolejki priorytetowej. Każde przesuwanie elementów w kolejce, które jest niezbędne przy ściąganiu z kolejki, wstawianiu do niej albo zmianie wagi wierzchołka, musisz odwzorować zmianą adresu tego wierzchołka w grafie, który to adres wskazuje na miejsce wierzchołka w kolejce priorytetowej.

dla tego wierzchołka odwiedzony := true;
w pozostałych wierzchołkach dajemy wagę dojścia na nieskończoność
repeat
    znajdujemy nieodwiedzony wierzchołek o najmniejszej wadze dojścia; 
    if są wierzchołki nieodwiedzone
    then
    begin
       znaleziony nieodwiedzony wierzchołek o najmniejszej wadze dojścia zaznaczamy jako odwiedzony;
       jeśli ten znaleziony  wierzchołek o najmniejszej wadze dojścia jest poszukiwanym wierzchołkiem
       then
          exit;
       for wszystkich nieodwiedzonych sąsiadów wierzchołka do
       begin
          if  waga dojścia dla sąsiada > waga dojścia do wierzchołka + waga między wierzchołkiem i sąsiadem
          then		
          begin
	     dla sąsiada waga dojścia := waga dojścia do wierzchołka + waga między wierzchołkiem i sąsiadem;
	     dla sąsiada wierzchołek poprzedni := wierzchołek;
          end
       end
    end   
until wszystkieWierzchołkiOdwiedzone;
od wybranego wierzchołka końcowego odczytuj wierzchołki poprzednie i rysuj rozwiązanie


1 użytkowników online, w tym zalogowanych: 0, gości: 1