Bevezetés a számításelméletbe 2 epizód tartalma:
Lépésről lépésre megnézzük, hogyan működik a Dijkstra algoritmus irányított gráfokban. Az élsúlyokkal ellátott gráfok minimális útjainak keresésére használjuk, az algoritmus irányított gráfokban is működik. Nézzük is meg.
És most nézzük meg, hogyan működik a Dijkstra algoritmus irányított gráfokban.
Az algoritmus lényege, hogy választunk egy pontot…
és ebből a pontból kiindulva csúcsról csúcsra haladva földerítjük az egész gráfot.
Megnézzük, hogy az 1-es csúcs közvetlen szomszédjai milyen távol vannak…
és szépen egyenként beírjuk a táblázatba.
Aztán amelyik csúcsról kiderül, hogy a legközelebb van…
annak a sorszámát beírjuk ide.
És ebből az új csúcsból megyünk tovább.
Megint kiválasztjuk a minimumot…
és a csúcs sorszámát beírjuk szépen ide, ahova kell.
Aztán ebből a csúcsból folytatjuk a felderítést.
Találtunk már ennél rövidebb utat is a 4-es csúcsba…
Úgyhogy ezt most szépen kicseréljük.
Aztán lássuk, mi van itt még…
Kiválasztjuk megint a legkisebbet…
és a csúcs sorszámát beírjuk ide, ahova kell.
Most a 4-es csúcsból folytatjuk a felderítést.
Nagy izgalmak itt nem lesznek.
És megyünk tovább az 5-ös csúcsból.
Végül itt a 7-es.
Hát, volt már jobb is…
A Dijkstra algoritmus távolság szerint felsorolta a gráf csúcsait.
Na persze ez a távolság mindig az 1-es csúcstól mért távolság.
Hogyha kíváncsiak vagyunk két tetszőlegesen kiválasztott csúcs távolságára…
akkor ebben egy újabb algoritmus fog tudni nekünk segíteni.
Bevezetés a számításelméletbe 2 epizód.