Keresse meg a legrövidebb utat két pont között egy grafikonon Dijkstra algoritmusával

A grafikon két pontja közötti legrövidebb út megtalálása általános probléma az adatstruktúrákban, különösen az optimalizálás során.

A grafikon élekkel összekötött csomópontok sorozata. A grafikonok súlyozhatók (az élek értékeket hordoznak) és irányítottak (az élek irányúak).

Ennek egyes alkalmazásai a repülési útvonal optimalizálása vagy 6 fokos Kevin Bacon.

Dijkstra algoritmusa

A probléma leggyakoribb megoldása a Dijkstra algoritmusa, amely frissíti a legrövidebb utat az aktuális csomópont és az összes szomszédja között.

Az összes szomszéd távolságának frissítése után a legkisebb távolságú csomópontra lép, és megismétli a folyamatot az összes meg nem látogatott szomszéddal. Ez a folyamat addig folytatódik, amíg a teljes grafikont meg nem tekintették.

A kódszintek képe

0. lépés:

Grafikonunkat be kell állítani, hogy rögzíteni tudjuk a szükséges értékeket. Bármelyik élen megvan a távolság a két csomópont között, amelyet összeköt. Bármelyik csomóponton a legrövidebb távolság van a kezdő csomóponttól.

Állítsuk az összes csomópont értékét pozitív végtelenre, és a kezdő csomópont értékét állítsuk nullára.

1. lépés:

Nézze meg az összes csomópontot közvetlenül a kezdő csomópont mellett. A kezdetet és ezeket a szomszédos csomópontokat összekötő élek által hordozott értékek az egyes csomópontoktól a legrövidebb távolságok.

Rögzítse ezeket a távolságokat a csomóponton - felülírva a végtelent -, és keresztezze is a csomópontokat, ami azt jelenti, hogy megtalálták a legrövidebb utat.

2. lépés:

Válassza ki az egyik csomópontot, amelynek a legrövidebb útját kiszámították, ezt hívjuk pivotunknak. Nézze meg a mellette levő csomópontokat (ezeket nevezzük célállomásoknak) és az őket elválasztó távolságokat.

Minden rendeltetési csomópontnál:

  • Ha az elfordulás és az azt összekötő élérték értéke kevesebb, mint a célcsomópont értéke, akkor frissítse az értékét, mivel új rövidebb útvonalat talált.
  • Ha a cél csomóponthoz vezető összes útvonal fel lett fedezve, akkor az áthúzható.

3. lépés:

Ismételje meg a 2. lépést, amíg az összes csomópontot nem lépte át. Most van egy grafikonunk, ahol bármelyik csomópontban tartott értékek a kezdő csomóponttól a legrövidebb távolságra lesznek tőle.

Több információ:

Bővebben Dijkstra algoritmusáról

Egyéb legrövidebb út algoritmusok