====== 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 <m 10>P=A_0, A_1, cdots, A_n=Q</m> pontokon keresztül. Ekkor <m 10>forall i <= n, i in bbN</m> esetén <m 10>A_0, A_1, cdots, A_i</m> minimális út //P// és //A<sub>i</sub>// között. Ha lenne ugyanis kisebb költségű út //P// és //A<sub>i</sub>// között, akkor <m 10>A_0, A_1, cdots, A_i</m> 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.

==== Példák ====

  * [[http://www.unf.edu/~wkloster/foundations/DijkstraApplet/DijkstraApplet.htm|Egy szemléltető applet]]
  * [[http://students.ceid.upatras.gr/~papagel/english/java_docs/minDijk.htm|Egy másik interaktív szemléltetés]]
  * [[http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml|És ha még nem volna elég...]]