1. feladat: Dijkstra algoritmus

Eredeti feladat

Határozza meg a Dijkstra algoritmus segítségével az F csúcsból az összes csúcsba a legolcsóbb utak költségeit! (A képen egy súlyozott gráf látható csúcsokkal A-tól J-ig). Csak a táblázat szürke részét kell kitölteni értelemszerűen!

Eredeti feladat képe

(Eredeti feladat képe)

Táblázat kitöltése lépésről lépésre (F-ből indulva)

A Dijkstra táblázatban minden sor egy "fixált" csúcsot jelent. Mindig a legkisebb aktuális értékkel rendelkező csúcsot választjuk ki.

LépésVálasztottABCDEGHJMagyarázat
0. - ∞∞∞∞∞∞∞∞ Kezdetben minden végtelen, az F értéke 0.
1. F (0) ∞∞∞∞1112∞10 F-ből elérhető: E(11), G(12), J(10).
2. J (10) ∞∞∞∞11122210 J-ből a H távolsága: 10+12=22.
3. E (11) ∞∞171811122010 E-ből: C(11+6=17), D(11+7=18), H javul(11+9=20).
4. G (12) ∞∞151811122010 G-ből: C javul(12+3=15).
5. C (15) 2224151811122010 C-ből: A(15+7=22), B(15+9=24). D(15+5=20) nem javít a 18-on.
6. D (18) 2224151811122010 D-ből az A(18+6=24) nem javít a 22-n.
7. H (20) 2224151811122010 H-ból a B(20+9=29) nem javít a 24-en.
8. A (22) 2224151811122010 A-ból a B(22+11=33) nem javít a 24-en.
9. B (24) 2224151811122010 Minden csúcs kész.

Megoldás menete (Logika)

  1. Inicializálás: Készítsünk egy táblázatot az összes csúccsal. A kezdőponthoz (F) írjunk 0-t, az összes többihez végtelent (∞).
  2. Kiválasztás: Válaszd ki a legkisebb értékű, még nem rögzített csúcsot.
  3. Frissítés (Relaxáció): Nézd meg az aktuális csúcs összes szomszédját. Ha az aktuális csúcs értéke + az él súlya kisebb, mint a szomszéd jelenlegi értéke, írd be az új, kisebb értéket.
  4. Ismétlés: Jelöld meg az aktuális csúcsot véglegesnek, és térj vissza a 2. lépéshez.

Felkészülés más számokra

Ha a gráf vagy a súlyok változnak, a módszer ugyanaz marad: