algorytm djikstra w zadaniu

pytanie zadane 24 kwietnia 2015 w C i C++ przez ziemjok Gaduła (4,160 p.)

Cześć

Jestem w trakcie (a raczej na początku :D) pisania pewnego algorytmu ale niestety nie od której strony to ugryźć.

Muszę napisać algorytm liczący najkrótszą drogę międzzy podanymi punktami. Program pobiera od użytkownika rozmiar (ilość kolumn i wierszy), punkt startowy i końcowy, wagi dla każdego pola.

Czytałem że należy użyć w tym zadaniu m. in algorytm djikstry, kopiec i listę, niestety nie wiem jak poprawnie to zaimplementować. Stworzyłem taką strukturę:

struct str{
	int wspx;
	int wspy;
	int indeks;
    int koszt_dojscia;
	int waga;
} pole[100];

zgodnie z tym co przecztałem w internecie ustawiam koszt_dojscia w każdym obiekcie pole na bardzo dużą wartość. Nie rozumiem jednak co mam robić dalej. Jak mam przesuwać się po tych polach(wg jakiej zasady) ,gdzie zapisywać obliczone odległości i co mam robićz polami które już obliczyłem?

z góry dzięki za pomoc

pozdrawiam

1 odpowiedź

odpowiedź 24 kwietnia 2015 przez Qhoros Mądrala (7,110 p.)

Algorytm Dijkstry to inaczej algorytm Prima. Te dwie osoby wymyśliły ten algorym niezależnie od siebie. ;) A teraz w czym rzecz. W tym algorytmie na samym początku wybieramy sobie dowolny wierzchołek. Tak jak piszesz wybiera go użytkownik. Następnie masz do wyboru wszystkie możliwe wyjścia z tego wierzchołka. Jednak jest to rodzaj algorymtu szukający MINIMALNEGO drzewa spinającego, dlatego musisz iść po ścieżce z najmniejszą wagą. Po dotarciu do drugiego wierzchołka musisz sprawdzić, spośród wszystkich możliwych (zatem uwzględniając także pierwszy wierzchołek) kolejną minimalną krawędź. Doszedłwszy to trzeciego wierzchołka musisz sprawdzać drogi wychodzące zarówno z pierwszego, drugiego jak i trzeciego wierzchołka i wybrać tą o najmniejszej wadze. Możesz sobie przejrzeć notatki z ćwiczeń z matematyki dyskretnej. Tam gdzie masz algorytm Kruskala zrób sobie metodą Dijkstry/Prima. Wynik minimalnego drzewa powinien wyjść identyczny jak metodą Kruskala.