Tartalomjegyzék
Minimális költségű út
Alapfeladat: Legyen G összefüggő, súlyozott gráf, tehát olyan gráf, melynek éleihez számokat rendelünk - ezek a költségek. Keressük a gráf P és Q pontja közötti utak közül a legkisebb összköltésgűt.
Legyen P és Q között egy minimális költségű út a pontokon keresztül. Ekkor
esetén
minimális út P és Ai között. Ha lenne ugyanis kisebb költségű út P és Ai között, akkor
helyett az eredeti útban is vehetnénk ezt az utat, így csökkentve a P és Q közötti út költségét, ami ellentmondana annak, hogy minimális költségű útból indultunk ki.
Dijkstra algoritmus
Módosított feladat: Keressük a gráf P-ből induló minimális költségű útjait a gráf összes pontjába.
Az algoritmus a futása során a G gráf minden egyes Q csúcspontjára nyilvántartja P csúcspont és a Q közötti, a futás során addig legrövidebbnek talált út költségét. Az algoritmus indulásakor ez az érték 0 a P pontra (d[P]=0), és végtelen a G gráf minden más pontjára. Ez megfelel annak a ténynek, hogy kezdetben nem ismerünk egyetlen utat sem, ami a P pontból a többi pontba vezetne. (d[Q]=∞ a V csúcshalmaz minden Q elemére, kivéve P-t.) Az algoritmus befejeződésekor a d[Q] az s-ből v-be vezető legrövidebb út költsége, ha létezik ilyen út - és végtelen, ha nincs ilyen út.
Az algoritmus az S és T ponthalmazokkal dolgozik. Az S halmaz tartalmazza G gráfnak azokat a pontjait, amelyekre d[Q] értéke már a legrövidebb út költségét adja meg, és a T halmaz tartalmazza a G gráf többi csúcspontját. Az S halmaz kezdetben az üres halmaz, és az algoritmus minden egyes iterációja során egy csúcspont átkerül a T halmazból az S halmazba. Ezt a csúcspontot úgy választjuk, hogy ennek legyen a legalacsonyabb a d[R] értéke. Amikor az R csúcspont átkerül T-ból S-be, az összes (R,Q) élre, azaz az R pont összes Q szomszédjára leellenőrzi az algoritmus, hogy az addig ismert legrövidebb utak tovább rövidíthetőek-e úgy, hogy vesszük a kiindulási ponttól az R-ig vezető legrövidebb utat és hozzáadjuk a (R,Q) él költségét. Ha így kisebb költségű utat kapunk, mint az eddig ismert legrövidebb út, akkor az algoritmus a d[Q] értékét ezzel az új, kisebb értékkel helyettesíti.
