Diszkrét matematika 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.

A képsor tartalma

É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.

 

Dijkstra algoritmus irányított gráfokban

03
hang
Hopsz, úgy tűnik nem vagy belépve, pedig itt olyan érdekes dolgokat találsz, mint például:

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.

Végül is miért ne néznél meg
még egy epizódot?
Ugrás az
összeshez