Vyhledávač spojení

danaceks:
Je to problém obchodného cestujúceho a keďže sa musíš pýtať tak ti ani neodporúčam sa snažiť to implementovať :) Pretože vytvoriť skutočne fungujúci a zároveň rýchly algoritmus je celkom náročné.
A minimálne budeš mať asi problém so získaním grafikonu (časového poriadku), polohy zastávok atď. Väčšinou tie dáta nebývajú verejné.

A keď sa môžem spýtať načo to chceš vytvárať? Žiadne z existujúcich riešení ti nevyhovuje?

Pcmanik: TSP je neco jineho. Tady jde o docela jednoduche prohledani grafu. Ale jak rikas, sehnani dat muze byt slozite.

Danaceks: pokud jsi o grafovych algoritmech neslysel, nepocitej s tim, ze neco rozumneho vytvoris. Pouzij existujici reseni.

danaceks:
Podívej se na procházení grafu do šířky a zamysli se nad uvedeným příkladem třeba tady - algoritmy.eu/zga/pruchod-grafu/bfs-hledani-nejkratsi-cesty.
Skok jezdcem po šachovnici je dobrý základní příklad. V další fázi je třeba představit si reálnou mapu jako takovouto matici vzdáleností, jednotlivé hrany (vzdálenosti mezi zastávkami) ohodnotit a uvažovat časy na přestupy.

danaceks:
Když ti dáme řešení, nepochopíš jej a budeš žadonit o každou jeho úpravu. Jedinou možností je, že se o to pokusíš sám a postupem času začneš chápat, jak to má fungovat.

V podstatě musíš přijmout terminologii grafů jako reprezentace stanic (vrcholů) propojených linkami (hrany). Pak se naučíš základní grafové algoritmy (procházení do šířky, do hloubky) a následně můžeš začít hledat nejkratší cestu.

Samozřejmě můžeš řešení nahackovat: každá linka bude prostý seznam stanic a ty budeš hledat pomocí in_array, zda linka spojuje počáteční a koncový bod. Můžeš dokonce najít linky obsahující počáteční a koncový bod a pak nad seznamy provést array_intersect. To umožní hledat cesty s jedním přestupem. Cokoli lepšího (víc přestupů, nejrychlejší cesty) vyžaduje použít grafové algoritmy.