Dijkstra algoritmus irányított gráfokban | mateking
 

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.

Egy lépésre vagy attól, hogy a matek melléd álljon és ne eléd.
  • Ez a legjobban áttekinthető, értelmezhető, használható és a legolcsóbb tanulási lehetőség.

    Eszter, 23
  • Nagyon jó árba van, valamint jobb és érthetőbb, mint sok külön matek tanár.

    Márk, 22
  • Jó árban van és hihetetlenül világos a magyarázat és annyiszor lehet visszatérni az egyes lépésekre, ahányszor arra csak szükség van a megértéshez.

    Lili, 22
  • Felsőbb éves egyetemisták ajánlották, "kötelező" címszóval.
    Ricsi, 19
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez