| dbo:abstract
|
- A Dijkstra-algoritmus egy mohó algoritmus, amivel irányított vagy irányítás nélküli gráfokban lehet megkeresni a legrövidebb utakat egy adott csúcspontból kiindulva. Az algoritmust Edsger Wybe Dijkstra holland informatikus fejlesztette ki. Az algoritmus inputja egy súlyozott G gráf és s a G gráf egy csúcsa. A s csúcs az út kiindulási pontja. Jelöljük V-vel a G gráf csúcsainak a halmazát, és legyen (u,v) a G gráf u-t v-vel összekötő éle, ahol u, v a gráf csúcsai. Jelöljük E-vel a G gráf éleinek a halmazát. Az élekhez rendelt súlyokat a w: E → [0,∞] súlyfüggvény adja meg, tehát w(u,v) az (u,v) él súlya. Az élekhez rendelt költségeket tekinthetjük a két csúcs közötti távolság általánosításának. Két csúcs közötti út költsége az úton lévő élek költségének az összege. Adott s és t V-beli csúcsokra az algoritmus megkeresi a legkisebb költségű s-ből t-be vezető utat (azaz a legrövidebb utat). Az algoritmus használható arra is, hogy adott pontból kiindulva a gráf összes többi pontjába vezető legrövidebb utakat megkeressük . (hu)
- A Dijkstra-algoritmus egy mohó algoritmus, amivel irányított vagy irányítás nélküli gráfokban lehet megkeresni a legrövidebb utakat egy adott csúcspontból kiindulva. Az algoritmust Edsger Wybe Dijkstra holland informatikus fejlesztette ki. Az algoritmus inputja egy súlyozott G gráf és s a G gráf egy csúcsa. A s csúcs az út kiindulási pontja. Jelöljük V-vel a G gráf csúcsainak a halmazát, és legyen (u,v) a G gráf u-t v-vel összekötő éle, ahol u, v a gráf csúcsai. Jelöljük E-vel a G gráf éleinek a halmazát. Az élekhez rendelt súlyokat a w: E → [0,∞] súlyfüggvény adja meg, tehát w(u,v) az (u,v) él súlya. Az élekhez rendelt költségeket tekinthetjük a két csúcs közötti távolság általánosításának. Két csúcs közötti út költsége az úton lévő élek költségének az összege. Adott s és t V-beli csúcsokra az algoritmus megkeresi a legkisebb költségű s-ből t-be vezető utat (azaz a legrövidebb utat). Az algoritmus használható arra is, hogy adott pontból kiindulva a gráf összes többi pontjába vezető legrövidebb utakat megkeressük . (hu)
|
| prop-hu:képLeírása
|
- Az a és b közötti legrövidebb út megkeresése Dijkstra-algoritmussal. Az algoritmus mindig a legkisebb távolságú még meg nem látogatott csúcsot választja, majd megnézi, hogy ezen csúcson keresztül mekkora út megtételével tudna eljutni egyes szomszédjaihoz. A csúcsot meglátogatottnak jelöli, ha végzett a szomszédok feldolgozásával. (hu)
- Az a és b közötti legrövidebb út megkeresése Dijkstra-algoritmussal. Az algoritmus mindig a legkisebb távolságú még meg nem látogatott csúcsot választja, majd megnézi, hogy ezen csúcson keresztül mekkora út megtételével tudna eljutni egyes szomszédjaihoz. A csúcsot meglátogatottnak jelöli, ha végzett a szomszédok feldolgozásával. (hu)
|
