Budowa programu na najkrótszą ścieżkę

pytanie zadane 8 lutego 2018 w C i C++ przez omen Nowicjusz (160 p.)

Witam, pracuję nad programem który liczy najkrótszą odległość pomiędzy dwoma miastami. Jestem beginnerem w języku C i potrafię użyć tylko podstaw. Niemniej jednak do wykonania mam zadanie i pragnę się dowiedzieć jak zacząć. Przejrzałem mnóstwo artykułów na ten temat i ile programistów tyle sposobów, ale większość zbyt skomplikowane. Czy powinienem użyć algorytmu? Jeśli tak to jakiego - miałem na oku Dijkstre, lecz nie do końca wiem jak go użyć. Czy da się w zwięzły sposób zawrzeć dane (współrzędne, albo odległości miast) w kodzie programu i operować tylko na tym (bez wczytywania zewnętrznego?) Jeśli ktoś może mnie na to naprowadzić, byłbym bardzo wdzięczny.

komentarz 9 lutego 2018 przez TenGumis Gaduła (3,440 p.)

Musisz precyzyjniej określić zadanie. Nie wiadomo z jakiego typu grafem mamy tutaj doczynienia aby wybrać odpowiedni algorytm.

1 odpowiedź

odpowiedź 8 lutego 2018 przez Wiciorny Ekspert (269,810 p.)

No przede-wszystkim to zadanie: które wymaga zastosowania algorytmu.

Dijkstra jest bardzo prostym algorytmem i łatwym do implementacji.

Jest jeszcze algorytm: A* - nieco trudniejszy i Belmana forda- ale to dobrze w pythonie zaimplementować.

Kieruj się strukturą grafu :) gdzie miastem będzie węzeł " tego grafu" a ściezki to będą krawędzie łączące, dodatkowo ich odległości " czyli WAGI KRAWĘDZI W GRAFIE' bedą intuicyjnie formalizować drogę i jej długość