Algorytm Dijkstry (z kopcem)

0

Szukam przykładowej implementacji algorytmu Dijkstry z kopcem, napisałem ten program z wyszukiwaniem linowym, rozumiem go, ale jak dochodzi do kopców to zaczynam się gubić... dlatego będę wdzięczny za jakiś gotowy kod do przeanalizowania.

0

Dzięki wielkie. Potrzebowałbym jeszcze ten algorytm napisany językiem naturalnym (pseudokod), ale znowu wersje z kopcem, wszystkie pseudokody jakie znalazłem w internecie są napisane bez kopca, a że kopiec to sprawa którą niedawno poznałem to pseudokod z kopcem bardzo ułatwiłby mi pisanie własnego kodu.

0

Algorytm jest ten sam i dla kopca i bez niego. Różni się tylko sposób przechowywania danych. Tu jest wszystko bardzo dobrze wytłumaczone:
http://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/Algorytmygrafowe-najl%C5%BCejsze%C5%9Bcie%C5%BCki

0

Dziękuję :)

0

Przepraszam za post pod postem, ale jakbyś mógł mi jeszcze powiedzieć co w pierwszym linku podanym przez ciebie oznacza zmienna n, bo na prawdę nie mam pomysłu. m to ilość krawędzi, ale n?

0

Ja obstawiam że liczba wierzchołków...

0

No właśnie też tak myślałem, ale to nie pasuje. Dajmy na to bardzo prosty graf:

        (3)

Jak wpiszę n = 3 (liczba wierzchołków?) i m = 2 (liczba krawędzi) to program po podaniu wszystkich danych się wsypuje i pisze ze vector is out of rage. Jak dam na to np. n = 10 (po prostu, większa liczba) i m =2 to wszystko jest ok i znajduje mi prawidłowo najkrótsza ścieżkę w grafie.

Jak już pytam, to normalne w tym algorytmie, że trzeba podawać długości 1-2, 2-3, a nie można 2-1, 3-2? Testowałem dwa różne programy i zawsze był wtedy błędy wynik. Potrzebna mi taka informacja, żeby wiedzieć, czy w swoim programie muszę przeciwdziałać takim sytuacjom, czy po prostu poinformować użytkownika o chronologicznym podawaniu odległości między węzłami.

0

Chłopie, to jest TWOJE zadanie domowe! Już sam fakt że ściągnąłeś je z internetu a nie napisałeś samemu jest karygodny, a ty jeszcze chcesz żebyśmy za ciebie przeanalizowali ten kod? ...

0

eh... krawędzie w tamtym kodzie są skierowane a wierzchołki numerowane od 0...

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