Optimāla transporta maršruta atrašana ar īsāku ceļu algoritmu

Individuālais uzdevums.

Atrast optimālo maršrutu, izmantojot sākuma datus, programmu īsāka ceļa noteikšanai un patstāvīgi sastādīto grafu. Sākuma dati iekļauj noteikto valsts (Somiju); ar programmas Google Maps palīdzību valsts teritorijā jāatradā pilsētas, jānoteic attālumus starp tām un jāsastādā maršrutu starp izvēlētām pilsētam. Jāuzzīmē atbilstošo grafu, kas sastāv no 8 virsotnem un ne mazāk kā 15 lokiem.

2. Grafa zīmējums.

Pirms grafa konstruēšanas pēc Google Maps kartes izvēlāmies 8 pilsētas Somijas teritorijā, kas atbilst grafa virsotnēm. Jāizmērā attālumus starp izvēlētām pilsētām (vienā un pretējā virzienos, tāpēc ka orientētājos grafos šie lielumi atšķiras); pie tām jāievēro, ka pilsētām jāsastādā maršrutu ar vienīgo sākuma punktu (sākuma virsotni). Var būt daudz variantu kādas pilsētas sasniegšanai no sākuma punkta. Ceļi no vienas pilsētas uz citām atbilst grafa lokiem ar noteikto garumu.…