„A számítástudomány alapjai - Segédanyagok a vizsgához” változatai közötti eltérés

## Kiválasztjuk a kezdőpontot és megjelöljük

## Meglátogatjuk az összes szomszédját, ahol még nem voltunk.

## Miután elfogytak a megjelölt pont még meg nem látogatott szomszédai, áttérünk a meglátogatott szomszédok közül a legkisebb indexűre és megjelöljük.

## Az előbbi két pontot ismételgetjük, amíg csak tudjuk.

## Kiválasztjuk a kezdőpontot.

## Felírjuk, hogy a kezdőpont mely szomszédjaiba milyen áron lehet eljutni. Amely pontba nem tudunk egy lépésben eljutni, azt végtelen eljutási költségnek jelöljük.

## Megnézzük, hogy a kiindulópontból hová juthatunk el a legolcsóbban, majd "felfedezzük" annak a pontnak a szomszédságát: felírjuk, hogy a '''kezdőpontból''' milyen költséggel juthatunk el ennek a pontnak a szomszédaihoz. Ha egy ponthoz olcsóbb eljutási lehetőséget találtunk, javítjuk. Ahol nem tudtunk javítani, változatlanul hagyjuk.

## Az előző pontot ismételgetjük addig, amíg már egy pontból sem tudunk javítani.

## Megszámozzuk az éleket tetszőleges sorrendben.

## Felírjuk, hogy a kiindulópontba 0 költségen, minden más pontba végtelen költségen juthatunk el.

## Számsorrendben, agyatlanul elkezdjük sorba venni az éleket és a Dijkstra-féle javítást próbáljuk elvégezni. Függetlenül attól, hogy mondjuk az adott él nagyon messze van a kiindulóponttól, és adott esetben egy olyan javítást akarunk elvégezni, hogy "ebbe a pontba végtelen költségen jutottam, tehát ennek a szomsédjába végtelen + 2-ért tudok". Ilyenkor belenyugszunk, hogy nem tudtunk javítani és vesszük a következő számú élt, hátha amentén tudunk.

## Az előbbi lépést ismételgetjük, addig, amíg a pontok számánál egyel kevesebbszer végig nem pörgettük az összes élt.

## Számozzuk meg a pontokat 1-től n-ig. Ez az algoritmus végigmegy minden ponton és ellenőrzi, hogy az adott ponton keresztül van-e rövidebb út bármely két pontpár között.

## Először rögzítsük, hogy az 1. ponton keresztül vezető utak hosszát keressük. (Ez legyen a "köztes állomás".)

## Majd rögzítsük, hogy az 1. pontból, az 1. ponton keresztül vezető utak hosszát keressük.

## Majd futtassuk végig, hogy az 1. pontból, az 1. ponton keresztül az 1., 2., 3., ... n. pontba milyen hosszúságú út vezet. Igen, a legelső lépésben az lesz az ellenőrzés tárgya, hogy "az 1. pontból az 1. pontba, majd az 1. pontból az 1. pontba vezető út rövidebb-e, mint az 1. pontból az 1. pontba vezető?".

## Miután ez megvan, térjünk vissza ennek a felsorolásnak a 3. lépéséhez, és rögzítsük, hogy a 2. pontból, az 1. ponton keresztül vezető utak hosszát keressük.

## Futtassuk végig a felsorolás 4. lépésének megfelelően a "célállomás" számát 1-től n-ig.

## Inkrementáljuk a "kiinduló állomást".

## Futtassuk le 1-től n-ig a célállomásokat.

## Ismételgessük az előző kettőt, amíg csak tudjuk. Ekkor inkrementáljuk a köztes állomás számát, amin keresztül keressük az utakat és kezdjük újból futtatni a kiinduló és célállomásokat.

## Vegyük észre, hogy ez három egymásba ágyzott for-ciklus. Mind 1-től n-ig megy, és a következőképpen vannak egymásba ágyazva: Keresztül(1..n){Kiinduló(1..n){Cél(1..n)}}

## Mindig akkor javítunk, ha Költség(Kiinduló->Köztes) + Költség(Köztes->Cél) < Költség(Kiinduló->Cél).