Najkratšia cesta

18th Nov 2026

Čo sa v cvičení naučíš

V tomto cvičení si precvičíš:

  • reprezentáciu váženého neorientovaného grafu,
  • hľadanie najkratšej cesty, keď spojenia majú rôzne vzdialenosti,
  • použitie prioritnej fronty na výber najbližšieho zatiaľ nespracovaného uzla,
  • zostavenie výslednej cesty z informácií o predchodcoch,
  • rozlišovanie rovnako krátkych ciest podľa lexikografického poradia.

Uzly sú očíslované od 0 po N - 1, kde N >= 1 je počet uzlov. Cieľom je vrátiť postupnosť uzlov od 0 po N - 1. Ak sa cieľ nedá dosiahnuť, výsledkom je prázdny zoznam. Ak má graf jediný uzol, výsledkom je [0]. Zo všetkých najkratších ciest máš vybrať lexikograficky najmenšiu.

Najprv si ukážeme základný Dijkstrov algoritmus, ktorý nájde jednu najkratšiu cestu. Dodatočnej požiadavke na lexikografický výber sa venuje samostatná časť na konci návodu.

Ako si predstaviť graf

Graf tvorí množina uzlov a spojení medzi nimi. Spojenia nazývame aj hrany a ich vzdialenosti váhy. Každé spojenie v tejto úlohe má podobu (uzol_a, uzol_b, vzdialenost). Vzdialenosti sú nezáporné, môžu teda byť aj nulové. Spojenie je obojsmerné: z a do b aj z b do a je rovnaká vzdialenosť.

Dva bežné spôsoby reprezentácie grafu sú:

  • zoznam susedov (adjacency list), ktorý pre každý uzol uchováva jeho susedov a vzdialenosti k nim,
  • matica susednosti (adjacency matrix), ktorej bunka [a][b] opisuje priame spojenie medzi uzlami a a b.

Reprezentácia grafu zoznamom susedov

V celom návode budeme používať graf so štyrmi uzlami a piatimi spojeniami. Jedep prvok zoznamu je trojica (uzil1, uzol2, vzdialenosť). Ku každému uzlu si poznačíme jeho susedov a vzdialenosť.

N = 4
spojenia = [(0, 1, 2), (0, 2, 5), (1, 2, 1), (1, 3, 3), (2, 3, 2)]

graf = {uzol: [] for uzol in range(N)}
for a, b, vzdialenost in spojenia:
    graf[a].append((b, vzdialenost))
    graf[b].append((a, vzdialenost))

Každé spojenie pridávame v oboch smeroch. Slovník vytvárame pre všetky uzly vrátane tých, ktoré nemajú žiadnych susedov. Výsledok je:

graf = {
    0: [(1, 2), (2, 5)],
    1: [(0, 2), (2, 1), (3, 3)],
    2: [(0, 5), (1, 1), (3, 2)],
    3: [(1, 3), (2, 2)],
}

Napríklad graf[1] obsahuje susedov uzla 1. Dvojica (2, 1) znamená, že do uzla 2 vedie priame spojenie so vzdialenosťou 1.

Dijkstrov algoritmus

Pre grafy s nezápornými vzdialenosťami sa hodí Dijkstrov algoritmus. Uchováva najmenšiu známu vzdialenosť od štartu ku každému uzlu. V každom kroku vyberie uzol s najmenšou známou vzdialenosťou a skúsi cez neho zlepšiť vzdialenosti k jeho susedom.

Vstupom je graf a štartovací uzol; prípadne aj cieľ, ak nás zaujíma iba cesta do jedného uzla. Základný postup s prioritnou frontou je:

  1. Vytvor zoznam vzdialeností uzlov. Štartu nastav vzdialenosť 0, ostatným uzlom nekonečno ∞. Do fronty vlož iba štart s prioritou 0.
  2. Vyber uzol s najmenšou vzdialenosťou. Ak je vzdiaalenosť uzla vo fronte iná ako vzdialenosť v zozname, ide o zastaraný záznam: preskoč ho.
  3. Pre každého suseda vypočítaj vzdialenosť cesty cez vybraný uzol. Ak je kratšia než doterajšia hodnota, aktualizuj vzdialenosť v zozname, zapamätaj si predchodcu a vlož ho do fronty s novou vzdialenosťou. Starý záznam vo fronte bude preskočený v bode 2.
  4. Opakuj výber, kým sa fronta nevyprázdni.

Keď v kroku 2 vyberieme aktuálny záznam uzla, jeho vzdialenosť je už najkratšia možná. Pri základnom algoritme preto môžeme skončiť aj pri výbere aktuálneho záznamu cieľa. To samo osebe ešte nezaručuje lexikograficky najmenšiu cestu.

Výstupom základného algoritmu sú najkratšie vzdialenosti a predchodcovia, z ktorých vieme zostaviť jednu najkratšiu cestu. Nedosiahnuteľným uzlom zostáva vzdialenosť ∞.

Iijkstrov algoritmus

Návrh v jazyku Python

Budeš potrebovať zoznam susedov graf z predchádzajúcej ukážky a dva slovníky. Jeden uchováva vzdialenosti od štartu, druhý predchodcov:

start = 0
ciel = N - 1
vzdialenosti = {uzol: float('inf') for uzol in range(N)}
predchodcovia = {uzol: None for uzol in range(N)}
vzdialenosti[start] = 0

Predchodca uzla je uzol, z ktorého doň prichádza aktuálna najlepšia cesta. Hodnota None znamená, že predchodca zatiaľ nie je určený; štart ho nepotrebuje. Existujúci zoznam susedov už znova neinicializuj, vymazal by si tým spojenia.

Práca s prioritnou frontou

Modul heapq poskytuje prioritnú frontu implementovanú ako binárna kopa. Do nej budeme ukladať dvojice (vzdialenost, uzol). Funkcia heappop vyberá dvojicu s najmenšou vzdialenosťou:

import heapq

fronta = []
heapq.heappush(fronta, (0, start))

Prioritu existujúceho záznamu nebudeme meniť. Keď nájdeme kratšiu cestu, vložíme nový záznam. Starší zostane vo fronte, ale pri výbere ho preskočíme. Nasledujúci cyklus nadväzuje na doterajšie ukážky a realizuje základný algoritmus bez lexikografického rozhodovania:

while fronta:
    vzdialenost, uzol = heapq.heappop(fronta)
    if vzdialenost > vzdialenosti[uzol]:
        continue
    # prejdeme všetkých susedov a pokračujeme v algoritme

Samostatná množina spracovaných uzlov tu nie je potrebná: nové záznamy vkladáme len pri striktne kratšej ceste a zastarané záznamy preskakujeme. Pri rovnakých vzdialenostiach porovná kopa čísla uzlov. Takéto poradie výberu však neurčuje lexikografické poradie celých ciest.

Priebeh na príklade

V našom grafe začíname v uzle 0. Zápisy vzdialeností a predchodcov v tabuľke sú v poradí uzlov 0, 1, 2, 3:

Krok Vzdialenosti Predchodcovia Čo sa zmenilo
Inicializácia [0, ∞, ∞, ∞] [None, None, None, None] Vo fronte je iba štart.
Spracovanie 0 [0, 2, 5, ∞] [None, 0, 0, None] Objavíme uzly 1 a 2.
Spracovanie 1 [0, 2, 3, 5] [None, 0, 1, 1] Zlepšíme cestu do 2 a objavíme 3.
Spracovanie 2 [0, 2, 3, 5] [None, 0, 1, 1] Cesta do 3 cez 2 má tiež dĺžku 5.
Preskočenie (5, 2) [0, 2, 3, 5] [None, 0, 1, 1] Uzol 2 už má vzdialenosť 3.
Spracovanie 3 [0, 2, 3, 5] [None, 0, 1, 1] Žiadna vzdialenosť sa nezlepší.

Priame spojenie 0–2 má dĺžku 5, ale cesta 0–1–2 má dĺžku 2 + 1 = 3. Preto sa vo fronte objavia záznamy (5, 2) aj (3, 2). Prvý z nich je pri neskoršom výbere už zastaraný.

Zostavenie výslednej cesty

Ak má cieľ stále vzdialenosť ∞, nie je dosiahnuteľný a vrátime prázdny zoznam. Inak od cieľa sledujeme predchodcov až po štart. Takto získaný zoznam nakoniec obrátime.

V našej ukážke sledujeme 3 → 1 → 0 a po obrátení dostaneme [0, 1, 3] s celkovou vzdialenosťou 5. Ide o jednu najkratšiu cestu; lexikografickú požiadavku ešte nespĺňa. Pri jedinom uzle vznikne [0]. Ak by sme pri rovnakých spojeniach zvýšili N na 5, uzol 4 by zostal izolovaný a výsledkom hľadania cesty z 0 do 4 by bolo [].

Najprv rozhoduje celková vzdialenosť. Len pri jej rovnosti porovnávame postupnosti uzlov lexikograficky: zľava doprava, pričom rozhoduje prvá odlišná hodnota. Cesty v tejto úlohe neobsahujú opakované uzly.

V našom grafe majú cesty [0, 1, 2, 3] aj [0, 1, 3] vzdialenosť 5. Lexikograficky menšia je [0, 1, 2, 3], pretože na prvej odlišnej pozícii platí 2 < 3. Počet uzlov cesty nerozhoduje.

Zložitosť

Pre základný Dijkstrov algoritmus so zoznamom susedov a binárnou kopou sa pri jednoduchom grafe (bez slučiek a viacnásobných hrán) bežne uvádza časová zložitosť O((N + E) log N) a pamäťová zložitosť O(N + E). Ukladáme graf, vzdialenosti, predchodcov a záznamy vo fronte. Rekonštrukcia jednej cesty trvá najviac O(N).

Pri použitom vkladaní nových záznamov môže kopa obsahovať až O(E) záznamov. Ak sú povolené aj viacnásobné hrany, všeobecnejší časový odhad je O(N + E log(E + 1)).

Tieto odhady sa týkajú základnej ukážky. Ak do riešenia pridáš uchovávanie, kopírovanie a porovnávanie celých ciest, musíš započítať aj ich náklady.

Užitočné odkazy

Previous Post

Najkratšia cesta