Üdvözöljük! Ha mindig is szerette volna megtanulni és megérteni Dijkstra algoritmusát, akkor ez a cikk az Ön számára készült. Látni fogja, hogyan működik a kulisszák mögött, lépésről-lépésre grafikus magyarázattal.
Tanulni fogsz:
- Alapvető grafikon fogalmak (gyors áttekintés).
- Mire használják Dijkstra algoritmusát.
- Hogyan működik a színfalak mögött, lépésről lépésre.
Kezdjük. ✨
? Bevezetés a grafikonokba
Kezdjük a grafikonok rövid bemutatásával.
Alapfogalmak
A grafikonok olyan adatstruktúrák, amelyeket az elempárok közötti "kapcsolatok" ábrázolására használnak.
- Ezeket az elemeket csomópontoknak nevezzük . Valódi tárgyakat, személyeket vagy entitásokat képviselnek.
- A csomópontok közötti kapcsolatokat éleknek nevezzük .
Ez egy grafikon grafikus ábrázolása:
A csomópontok színes körökkel, az élek pedig vonalakkal vannak ábrázolva, amelyek összekötik ezeket a köröket.
? Tipp: Két csomópont csatlakozik, ha van él közöttük.
Alkalmazások
A grafikonok közvetlenül alkalmazhatók a valós forgatókönyvekre. Például grafikonokkal modellezhetünk egy közlekedési hálózatot, ahol a csomópontok olyan létesítményeket képviselnek, amelyek termékeket küldenek vagy fogadnak, az élek pedig az őket összekötő utakat vagy utakat (lásd alább).
A grafikonok típusai
A grafikonok a következők lehetnek:
- Irányítatlan: ha minden összekapcsolt csomópont-pár esetében mindkét irányban haladhat egyik csomópontról a másikra.
- Irányított: ha minden összekapcsolt csomópont-pár esetében csak az egyik csomópontról a másikra léphet egy adott irányban. Nyílokat használunk egyszerű vonalak helyett az irányított élek ábrázolásához.
? Tipp: ebben a cikkben irányítatlan grafikonokkal fogunk dolgozni .
Súlyozott grafikonok
A súlygrafikon olyan gráf, amelynek élei "súlygal" vagy "költséggel" rendelkeznek. Az él súlya képviselheti a távolságot, az időt vagy bármit, ami modellezi az összekötött csomópontpár közötti "kapcsolatot".
Például az alábbi súlyozott grafikonon egy kék szám látható az egyes élek mellett. Ez a szám a megfelelő él súlyának képviseletére szolgál.
? Tipp: Ezek a súlyok elengedhetetlenek a Dijkstra algoritmusához. Egy pillanat alatt meglátja, miért.
? Bevezetés Dijkstra algoritmusába
Most, hogy ismeri a grafikonok alapfogalmait, kezdjük el merülni ezt a csodálatos algoritmust.
- Cél és felhasználási esetek
- Történelem
- Az algoritmus alapjai
- Követelmények
Cél és felhasználási esetek
Dijkstra algoritmusa segítségével megtalálja a legrövidebb utat a csomópontok között egy grafikonon. Különösen megtalálja a legrövidebb utat egy csomóponttól (az úgynevezett "forrás csomópont") a grafikon összes többi csomópontjáig , így létrehozva a legrövidebb út fáját.
Ezt az algoritmust a GPS-eszközök használják arra, hogy megtalálják a legrövidebb utat az aktuális hely és a cél között. Széles alkalmazási területe van az iparban, különösen olyan területeken, ahol modellezési hálózatokra van szükség.
Történelem
Ezt az algoritmust Dr. Edsger W. Dijkstra, egy zseniális holland informatikus és szoftvermérnök hozta létre és tette közzé.
1959-ben 3 oldalas cikket tett közzé "Megjegyzés két problémáról a grafikonokkal való összefüggésben" címmel, ahol elmagyarázta új algoritmusát.
Egy 2001-es interjú során Dr. Dijkstra elárulta, hogyan és miért tervezte meg az algoritmust:
Mi a legrövidebb út Rotterdam és Groningen között? Ez a legrövidebb út algoritmusa, amelyet körülbelül 20 perc alatt megterveztem. Egy reggel Amszterdamban vásároltam fiatal menyasszonyommal, és fáradtan leültünk a kávézó teraszára, hogy igyunk egy csésze kávét, és éppen azon gondolkodtam, hogy meg tudom-e ezt csinálni, majd megterveztem az algoritmust a legrövidebb útra . Mint mondtam, ez egy 20 perces találmány volt. Valójában 1959-ben jelent meg, három évvel később. A kiadvány még mindig nagyon szép. Az egyik oka annak, hogy ilyen szép, hogy ceruza és papír nélkül terveztem. Ceruza és papír nélkül szinte kénytelen elkerülni az összes elkerülhető összetettséget. Végül ez az algoritmus nagy csodálkozásomra hírnevem egyik alappillére lett. - Amint azt az Edsger W. cikk idéziDijkstra az Edsger W. Dijkstrával készített interjúból.⭐ Hihetetlen, nem? Mindössze 20 perc alatt Dr. Dijkstra megtervezte a számítástechnika történetének egyik leghíresebb algoritmust.
Dijkstra algoritmusának alapjai
- Dijkstra algoritmusa alapvetően a választott csomópontnál kezdődik (forráscsomópont), és elemzi a grafikont, hogy megtalálja a legrövidebb utat az adott csomópont és az összes többi csomópont között.
- Az algoritmus nyomon követi az egyes csomópontok és a forráscsomópontok közötti jelenleg ismert legrövidebb távolságot, és frissíti ezeket az értékeket, ha rövidebb utat talál.
- Miután az algoritmus megtalálta a legrövidebb utat a forrás csomópont és egy másik csomópont között, akkor ezt a csomópontot "meglátogatottként" jelölik és hozzáadják az útvonalhoz.
- A folyamat addig folytatódik, amíg a grafikon összes csomópontja hozzá nem kerül az útvonalhoz. Így van egy olyan utunk, amely összeköti a forrás csomópontot az összes többi csomóponttal, az egyes csomópontok eléréséhez a lehető legrövidebb utat követve.
Követelmények
Dijkstra algoritmusa csak pozitív súlyú grafikonokkal működhet . Ennek oka, hogy a folyamat során hozzá kell adni az élek súlyát a legrövidebb út megtalálásához.
Ha negatív súly van a grafikonon, akkor az algoritmus nem fog megfelelően működni. Miután egy csomópontot "meglátogatottként" jelöltek meg, az adott csomóponthoz vezető aktuális útvonalat az adott csomópont eléréséhez szükséges legrövidebb útként jelöljük meg. A negatív súlyok pedig megváltoztathatják ezt, ha a teljes tömeg csökkenthető, miután ez a lépés megtörtént.
? Példa Dijkstra algoritmusára
Most, hogy többet tud erről az algoritmusról, nézzük meg, hogyan működik a színfalak mögött, lépésről lépésre.
Ez a grafikon van:
Az algoritmus a legrövidebb utat generálja a 0csomóponttól a grafikon összes többi csomópontjáig.
? Tipp: Ennél a grafikonnál feltételezzük, hogy az élek súlya képviseli a két csomópont közötti távolságot.
A grafikon minden csomópontjánál a legrövidebb útvonal lesz csomópontról 0csomópontra 1, csomópontról 0csomópontra 2, csomópontról 0csomópontra 3és így tovább.
Kezdetben ez a távolságlistánk van (kérjük, olvassa el az alábbi listát):
- A forrás csomópont és a saját távolsága
0. Ebben a példában a forráscsomópont csomópont lesz,0de bármely tetszőleges csomópont lehet. - A forrás csomópont és az összes többi csomópont közötti távolságot még nem határozták meg, ezért ezt kezdetben a végtelen szimbólummal ábrázoljuk.
Ez a lista (lásd alább) is megvan, hogy nyomon kövessük azokat a csomópontokat, amelyeket még nem látogattunk meg (azokat a csomópontokat, amelyek nem kerültek be az útvonalba):
? Tipp: Ne feledje, hogy az algoritmus elkészült, miután az összes csomópont hozzá lett adva az útvonalhoz.
Mivel a csomóponton való indulást választjuk 0, meglátogathatjuk ezt a csomópontot. Ezzel egyenértékűen kiemeljük a nem meglátogatott csomópontok listájáról, és egy piros szegélyt adunk a diagram megfelelő csomópontjához:
Most el kell kezdenünk ellenőrizni a csomópont 0és a szomszédos csomópontok közötti távolságot . Mint látható, ezek csomópontok 1és 2(lásd a piros széleket):
? Tipp: Ez nem azt jelenti, hogy azonnal hozzáadjuk a két szomszédos csomópontot a legrövidebb útvonalhoz. Mielőtt csomópontot adna ehhez az útvonalhoz, ellenőriznünk kell, hogy megtaláltuk-e a legrövidebb utat az eléréséhez. Egyszerűen elvégezzük az első vizsgálati folyamatot, hogy lássuk a rendelkezésre álló lehetőségeket.
Frissítenünk kell a 0csomópontok 1és a csomópontok közötti távolságot az 2őket csomóponthoz 0(a forrás csomóponthoz) kötő élek súlyával. Ezek a súlyok 2, illetve 6:
A szomszédos csomópontok távolságának frissítése után:
- Az aktuális ismert távolságok alapján válassza ki azt a csomópontot, amely a legközelebbi a forrás csomóponthoz.
- Jelölje meglátogatottként.
- Adja hozzá az útvonalhoz.
Ha megnézzük a távolságok listáját, láthatjuk, hogy a csomópontnak 1a legrövidebb távolsága van a forrás csomópontjától (2 távolság), ezért hozzáadjuk az útvonalhoz.
Az ábrán ezt piros éllel ábrázolhatjuk:
Vörös négyzettel jelöljük a listában, hogy jelezzük, hogy "meglátogatták", és hogy megtaláltuk a legrövidebb utat ehhez a csomóponthoz:
Kihúzzuk a nem látogatott csomópontok listájáról:
Most elemeznünk kell az új szomszédos csomópontokat, hogy megtaláljuk a hozzájuk vezető legrövidebb utat. Csak azokat a csomópontokat fogjuk elemezni, amelyek szomszédosak a már a legrövidebb út részét képező csomópontokkal (piros élekkel jelölt út).
A csomópont 3és a csomópont 2mindkettő szomszédos azokkal a csomópontokkal, amelyek már az útvonalon vannak, mert közvetlenül kapcsolódnak 0csomóponthoz 1, illetve csomóponthoz , amint az alább látható. Ezeket a csomópontokat elemezzük a következő lépésben.
Mivel a forrás csomópont és a csomópont közötti távolság már szerepel a listánkban, 2ezúttal nem kell frissítenünk a távolságot. Csak a forrás csomópont és az új szomszédos csomópont (csomópont 3) közötti távolságot kell frissítenünk :
Ez a távolság 7 . Lássuk miért.
Ahhoz, hogy megtalálja a távolságot a forrás csomóponttól egy másik csomópontig (ebben az esetben csomópont 3), hozzáadjuk az összes él súlyát, amelyek a legrövidebb utat képezik az adott csomópont eléréséhez:
- Csomópont esetén
3: a teljes távolság 7, mert összeadjuk az útvonalat alkotó élek súlyát0 -> 1 -> 3(2 az élhez0 -> 1és 5 az élhez1 -> 3).
Most, hogy megvan a távolság a szomszédos csomópontoktól, ki kell választanunk, melyik csomópont kerül hozzá az útvonalhoz. Ki kell választanunk azt a meg nem látogatott csomópontot, amely a lehető legrövidebb (jelenleg ismert) távolsággal rendelkezik a forrás csomópontjától.
A távolságok listájából azonnal észlelhetjük, hogy ez a 6.2 távolságú csomópont :
Grafikusan hozzáadjuk az útvonalhoz, a csomópont körül piros szegéllyel és egy piros éllel:
Meglátogatottként is megjelöljük, ha egy kis piros négyzetet adunk a távolságok listájához, és áthúzjuk a nem látogatott csomópontok listájáról:
Most meg kell ismételnünk a folyamatot, hogy megtaláljuk a legrövidebb utat a forrás csomóponttól az új szomszédos csomópontig, amely csomópont 3.
Láthatja, hogy két lehetséges utunk van, 0 -> 1 -> 3ill 0 -> 2 -> 3. Nézzük meg, hogyan tudjuk eldönteni, melyik a legrövidebb út.
A csomópont 3már rendelkezik a korábban rögzített távolsággal ( 7, lásd az alábbi listát). Ez a távolság egy előző lépés eredménye volt, ahol összeadtuk a két él 5. és 2. súlyát, amelyeket át kellett lépnünk, hogy kövessük az utat 0 -> 1 -> 3.
De most van egy másik alternatívánk. Ha úgy döntünk, hogy kövesse az utat 0 -> 2 -> 3, mi lenne szükség, hogy kövesse két szélét 0 -> 2, és 2 -> 3súlyokkal 6 és 8 ,illetőleg,amely összesen 14 távolságot jelent .
Nyilvánvaló, hogy az első (meglévő) távolság rövidebb (7 vs. 14), ezért úgy döntünk, hogy megtartjuk az eredeti utat 0 -> 1 -> 3. Csak akkor frissítjük a távolságot, ha az új út rövidebb.
Ezért hozzá ez a csomópont a pálya az első alternatíva: 0 -> 1 -> 3.
Megjelöljük ezt a csomópontot látogatottként, és kiemeljük a nem látogatott csomópontok listájáról:
Most megismételjük a folyamatot.
Ellenőriznünk kell az új szomszédos csomópontokat, amelyeket eddig nem látogattunk meg. Ezúttal ezek a csomópontok csomópontok 4és csomópontok, 5mivel szomszédosak a csomópontokkal 3.
Frissítjük e csomópontok távolságát a forrás csomópontig, mindig megpróbálunk rövidebb utat találni, ha lehetséges:
- Csomópont esetén
4: a távolság 17 az úttól0 -> 1 -> 3 -> 4. - Csomópont esetén
5: a távolság 22 az úttól0 -> 1 -> 3 -> 5.
? Tipp: Vegye figyelembe, hogy csak a legrövidebb (piros színnel jelölt) út meghosszabbítását vehetjük figyelembe. Nem vehetünk figyelembe olyan utakat, amelyek olyan éleken vezetnek át bennünket, amelyek nem kerültek hozzá a legrövidebb útvonalhoz (például nem tudunk kialakítani egy olyan utat, amely átmegy az élen 2 -> 3).
Ki kell választanunk, hogy melyik meg nem látogatott csomópont lesz most meglátogatva. Ebben az esetben ez a csomópont, 4mert a távolságok listájában a legrövidebb távolság van. Grafikusan hozzáadjuk a diagramhoz:
"Meglátogatottként" is megjelöljük egy kis piros négyzet hozzáadásával a listába:
És kiiktatjuk a nem látogatott csomópontok listájáról:
És megismételjük a folyamatot. Ellenőrizzük a szomszédos csomópontokat: csomópont 5és csomópont 6. Elemeznünk kell minden lehetséges utat, amelyet követhetünk, hogy elérjük azokat a csomópontoktól, amelyeket már meglátogattunk látogatottként és hozzáadtunk az útvonalhoz.
Csomópont esetén 5:
- Az első lehetőség az út követése
0 -> 1 -> 3 -> 5, amelynek távolsága 22 a forrás csomópontjától (2 + 5 + 15). Ezt a távolságot már egy korábbi lépésben rögzítették a távolságok listáján. - A második lehetőség az útvonal követése lenne
0 -> 1 -> 3 -> 4 -> 5, amelynek távolsága 23 a forrás csomópontjától (2 + 5 + 10 + 6).
Nyilvánvaló, hogy az első útvonal rövidebb, ezért a csomópont számára választjuk 5.
Csomópont esetén 6:
- A rendelkezésre álló útvonal
0 -> 1 -> 3 -> 4 -> 6, amelynek távolsága 19 a forrás csomópontjától (2 + 5 + 10 + 2).
A csomópontot a legrövidebb (jelenleg ismert) távolsággal jelöljük meglátogatottként. Ebben az esetben csomópont 6.
És kiiktatjuk a nem látogatott csomópontok listájáról:
Most megvan ez az út (piros színnel jelölve):
Csak egy csomópontot még nem látogattunk meg, csomópont 5. Lássuk, hogyan tudjuk beilleszteni az útba.
Három különböző útvonalon haladhatunk, hogy elérjük 5a csomópontot az útvonalhoz hozzáadott csomópontoktól:
- 1. lehetőség: 22
0 -> 1 -> 3 -> 5távolsággal (2 + 5 + 15). - 2. lehetőség: 23
0 -> 1 -> 3 -> 4 -> 5távolsággal (2 + 5 + 10 + 6). - 3. lehetőség: 25
0 -> 1 -> 3 -> 4 -> 6 -> 5távolsággal (2 + 5 + 10 + 2 + 6).
Kiválasztjuk a legrövidebb utat: 22-es0 -> 1 -> 3 -> 5 távolsággal .
Megjelöljük a csomópontot látogatottként, és kiemeljük a nem látogatott csomópontok listájáról:
És voilà! Megvan a végeredmény, a legrövidebb úttal a csomópontok 0és a csomópontok között a grafikonon.
Az ábrán a piros vonalak jelölik a legrövidebb útvonalhoz tartozó éleket. Ezeket az éleket kell követnie ahhoz, hogy a grafikon adott csomópontjához a legrövidebb utat kövesse, a csomóponttól kezdve 0.
Például, ha el akarja érni a csomópontot a csomóponttól 6kezdve 0, akkor csak a piros széleket kell követnie, és 0 -> 1 -> 3 -> 4 - > 6automatikusan a legrövidebb utat fogja követni .
? Összefoglalva
- A grafikonok objektumok, emberek vagy entitások közötti kapcsolatok modellezésére szolgálnak. Két fő elemük van: csomópontok és élek. A csomópontok objektumokat, az élek pedig az ezen objektumok közötti kapcsolatokat képviselik.
- Dijkstra algoritmusa megtalálja a legrövidebb utat egy adott csomópont (az úgynevezett "forráscsomópont") és az összes többi csomópont között egy grafikonon.
- Ez az algoritmus az élek súlya alapján megtalálja azt az utat, amely minimalizálja a forrás csomópont és az összes többi csomópont közötti teljes távolságot (súlyt).
Nagyon remélem, hogy tetszett a cikkem, és hasznosnak találta. Most már tudja, hogyan működik Dijkstra algoritmusa a színfalak mögött. Kövessen a Twitteren @EstefaniaCassN, és nézze meg online tanfolyamaimat.