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
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/Algorytmy_grafowe_-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:
(1)------(2)
|
|
(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...