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

Számítástudomány alapjai 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.
  • A mateking miatt sikerült az érettségi és az összes egyetemi matekos tárgyam.

    Míra, 21
  • Olyan weboldal, ami még egy vak lovat is megtanítana integrálni.

    Petra, 26
  • Otthonról elérhető és olcsóbb, mint egy magántanár és akkor használom, amikor akarom.

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

    Márk, 22
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez