Znalezienie najkrótszej trasy między dwoma miastami – pomoc z rozpoczęciem pisania kodu programu

0

Witam, mam problem z napisaniem projektu, a dokładniej nie wiem jak zacząć. Bardzo proszę o pomoc w rozpoczęciu programu. Graf BFS, drzewo, listy ? Co tutaj wykorzystać i w jaki sposób ?

Napisać program, który umożliwia znalezienie najkrótszej trasy między dwoma miastami. Miasta połączone są drogami o pewnej długości. Drogi są jednokierunkowe. Plik mapy dróg ma następującą postać: W każdej linii podana jest jedna droga:

<miasto początkowe> <miasto końcowe>  <odległość>

Przykładowy plik dróg (liczba dróg nie jest ograniczona):

Katowice Krakow 70 
Krakow Tarnow 70
 Tarnow Jaslo 50 
Katowice Gliwice 22
 Lodz Poznan 205
 Gliwice Katowice 22 
Katowice Czestochowa 70 
Czestochowa Lodz 120 
Lodz Torun 165 
Krakow Katowice 70 
Gliwice Wroclaw 180

Drugim plikiem wejściowym jest plik z trasami do wyznaczenia. Każda linia pliku zawiera jedną trasę w postaci:

<miasto początkowe> <miasto końcowe>

Przykładowy plik tras do wyznaczenia (liczba tras nie jest ograniczona):

Katowice Torun
 Krakow Poznan
 Tarnow Wroclaw

Wynikiem działania programu jest plik wyjściowy z wyznaczonymi trasami, tzn. podana jest nazwa trasy, całkowita długość, a potem poszczególne odcinki z długościami, np. trasa: Katowice --> Torun (355 km):

Katowice --> Czestochowa 70
 Czestochowa --> Lodz 120 
Lodz --> Torun 165
3

Brzmi jak zadanie dla Dijkstry albo BFS.

0

kq miał tu na myśli - góglaj frazę "algortym Djikstry" albo "algorytm BFS"

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