Tekintsük a legrövidebb út megtalálásának példáját. Adott a város régióit összekötő autópálya-hálózat. Egyes utak egyirányúak. Keresse meg a legrövidebb utakat a városközpontból a környék minden városába.
A probléma megoldásához használhatja Dijkstra algoritmusa- egy gráfalgoritmus, amelyet E. Dijkstra holland tudós talált fel 1959-ben. Megkeresi a gráf egyik csúcsa és a többi csúcs közötti legrövidebb távolságot. Csak negatív súlyú élek nélküli gráfokhoz működik.
Meg kell találni a legrövidebb távolságokat az 1. csúcstól az összes többiig.
A körök a csúcsokat, a vonalak a köztük lévő utakat (a gráf éleit) jelölik. A csúcsok száma a körökben van feltüntetve, súlyuk az élek felett van feltüntetve - az út hossza. Minden csúcs mellett egy piros címke van megjelölve - az ehhez a csúcshoz vezető legrövidebb út hossza az 1. csúcstól.
Magának az 1-es csúcsnak a címkéjét 0-nak tételezzük fel, a többi csúcs címkéi elérhetetlenek nagy szám(ideális esetben - a végtelen). Ez azt tükrözi, hogy az 1. csúcs és a többi csúcs közötti távolság még nem ismert. A gráf minden csúcsa nem látogatottként van megjelölve. 
Első lépés
Az 1-es csúcsnak van minimális címkéje, a 2-es, 3-as és 6-os csúcsok a szomszédai. A csúcs szomszédjait sorra megkerüljük.
Az 1. csúcs első szomszédja a 2. csúcs, mert az oda vezető út hossza minimális. A hozzá vezető út hossza az 1-es csúcson át egyenlő az 1-es csúcshoz vezető legrövidebb távolság összegével, a címkéjének értékével és az 1-től a 2-ig tartó él hosszának összegével, azaz 0 + 7 = 7. Ez kevesebb, mint a 2. csúcs jelenlegi címkéje (10000), így a 2. csúcs új címkéje 7. 
Hasonlóképpen megtaláljuk az összes többi szomszéd úthosszát (3. és 6. csúcs).
Az 1. csomópont összes szomszédja ellenőrzésre kerül. A jelenlegi minimális távolság az 1. csúcsig véglegesnek minősül, és nem módosítható. Az 1. csúcs meglátogatottként van megjelölve.
Második lépés
Az algoritmus 1. lépése megismétlődik. Ismét megtaláljuk a „legközelebbi” a nem látogatott csúcsokat. Ez a 7-es jelölésű 2. csúcs.
Ismét megpróbáljuk csökkenteni a kiválasztott csúcs szomszédjainak címkéit, megpróbálva átjutni rajtuk a 2. csúcson. A 2. csúcs szomszédai az 1., 3. és 4. csúcsok.
Az 1. csúcsot már meglátogatták. A 2. csúcs következő szomszédja a 3. csúcs, mivel ezen van a látogatatlanként megjelölt csúcsok minimális címkéje. Ha 2-n keresztül megy hozzá, akkor egy ilyen út hossza 17 lesz (7 + 10 = 17). De a harmadik csúcs jelenlegi címkéje 9 és 9< 17, поэтому метка не меняется.
A 2. csúcs másik szomszédja a 4. csúcs. Ha a 2. csúcson keresztül megyünk hozzá, akkor egy ilyen út hossza 22 lesz (7 + 15 = 22). 22 óta<10000, устанавливаем метку вершины 4 равной 22.
A 2. csúcs összes szomszédja meg van nézve, ezért meglátogatottként jelöljük meg.
Harmadik lépés
Az algoritmus lépését megismételjük a 3. csúcs kiválasztásával. Ennek „feldolgozása” után a következő eredményeket kapjuk. 
Negyedik lépés
Ötödik lépés
hatodik lépés
Így a legrövidebb út az 1-es csúcstól az 5-ös csúcsig a csúcsokon át vezető út lesz 1 — 3 — 6 — 5
, hiszen így minimum 20 súlyt hízunk.
Nézzük a legrövidebb utat. Ismerjük az egyes csúcsok útvonalának hosszát, és most a csúcsokat fogjuk figyelembe venni a végétől. Tekintsük a végső csúcsot (ebben az esetben a csúcsot 5
), és minden olyan csúcsra, amelyhez kapcsolódik, úgy határozzuk meg az út hosszát, hogy kivonjuk a megfelelő él súlyát a végső csúcs úthosszából.
Igen, felső 5
úthossza van 20
. A csúcshoz kapcsolódik 6
és 4
.
A tetejére 6
szerezd meg a súlyt 20-9 = 11 (egyezik).
A tetejére 4
szerezd meg a súlyt 20-6 = 14 (nem egyezik).
Ha ennek eredményeként olyan értéket kapunk, amely megegyezik a kérdéses csúcs (ebben az esetben a csúcs) úthosszával 6
), akkor ebből történt az átmenet a végső csúcsba. Ezt a csúcsot megjelöljük a kívánt útvonalon.
Ezután meghatározzuk azt az élt, amelyen keresztül eljutottunk a csúcshoz 6
. És így tovább, amíg el nem érünk az elejére.
Ha egy ilyen bejárás eredményeként egy lépésben több csúcsra ugyanazok az értékek vannak, akkor bármelyiket megtehetjük - több út azonos hosszúságú lesz.
Dijkstra algoritmusának megvalósítása
A grafikon súlyainak tárolására négyzetmátrixot használnak. A gráf csúcsai a sorok és oszlopok fejlécében találhatók. A gráfívek súlyai pedig a táblázat belső celláiba kerülnek. A gráf nem tartalmaz ciklusokat, így a mátrix főátlója nulla értékeket tartalmaz.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 7 | 9 | 0 | 0 | 14 |
| 2 | 7 | 0 | 10 | 15 | 0 | 0 |
| 3 | 9 | 10 | 0 | 11 | 0 | 2 |
| 4 | 0 | 15 | 11 | 0 | 6 | 0 |
| 5 | 0 | 0 | 0 | 6 | 0 | 9 |
| 6 | 14 | 0 | 2 | 0 | 9 | 0 |
Megvalósítás C++ nyelven
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#define _CRT_SECURE_NO_WARNINGS
#beleértve
#beleértve
#define MÉRET 6
int main()
{
int a; // kapcsolatok mátrixa
int d; // minimális távolság
intv; // meglátogatott csúcsok
int temp, miniindex, min;
int kezd_index = 0;
system("chcp 1251" );
system("cls" );
// A kapcsolati mátrix inicializálása
for (int i = 0; i
a[i][i] = 0;
for (int j = i + 1; j
scanf("%d" , &temp);
a[i][j] = hőmérséklet;
a[j][i] = hőmérséklet;
}
}
// A kapcsolati mátrix megjelenítése
for (int i = 0; i
for (int j = 0; j
printf("\n");
}
//Csúcsok és távolságok inicializálása
for (int i = 0; i
d[i] = 10000;
v[i] = 1;
}
d=0;
// Algoritmus lépés
do(
miniindex = 10000;
min = 10000;
for (int i = 0; i
if ((v[i] == 1) && (d[i]
min = d[i];
miniindex=i;
}
}
// Adja hozzá a talált minimális súlyt
// az aktuális csúcssúlyhoz
// és hasonlítsa össze az aktuális minimális csúcssúllyal
ha (minindex != 10000)
{
for (int i = 0; i
ha (a[i] > 0)
{
hőmérséklet = min + a[i];
ha (hőm< d[i])
{
d[i] = hőmérséklet;
}
}
}
v = 0;
}
) while (minindex< 10000);
// A csúcsok legrövidebb távolságának megjelenítése
printf( "\nLegrövidebb távolságok a csúcsoktól: \n");
for (int i = 0; i
// Útvonal visszaállítása
intver; // látogatott csúcsok tömbje
int end = 4; // végcsúcs index = 5 - 1
ver = vége + 1; // kezdőelem - végcsúcs
int k = 1; // az előző csúcs indexe
int súly = d; // végcsúcs súlya
while (vége != kezdő_index) // amíg el nem érjük a kezdő csúcsot
{
for (int i = 0; i
ha (a[i] != 0) // ha van kapcsolat
{
int hőmérséklet = tömeg - a[i]; // határozza meg az útvonal súlyát az előző csúcsból
ha (hőmérséklet == d[i]) // ha a súly megegyezik a számítottkal
{ // ez azt jelenti, hogy ebből a csúcsból átmenet történt
súly = hőmérséklet; // tárolja az új súlyt
vége = i; // az előző csúcs mentése
ver[k] = i + 1; // és írd egy tömbbe
k++;
}
}
}
// Az útvonal megjelenítése (a kezdő csúcs a k elemből álló tömb végén van)
printf( "\nA legrövidebb kimeneti útvonal\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d " , ver[i]);
getchar(); getchar();
visszatérés 0;
}
A végrehajtás eredménye
Vissza:
A Dijkstra algoritmusa egy gráfalgoritmus, amelyet E. Dijkstra holland tudós talált fel 1959-ben. Megkeresi a gráf egyik csúcsától a legrövidebb távolságot az összes többihez. Az algoritmus csak negatív súlyú élek nélküli gráfokra működik. széles körben használják a programozásban és az olyan technológiákban, mint az OSPF, és a visszacsatolási útvonalak kiküszöbölésére használja, más néven a legrövidebb út először.
Dijkstra algoritmusa megoldja az egycsúcsos legrövidebb út problémáját egy súlyozott irányított, s kezdeti csúcsú G = (V, E) gráfra, amelyben az összes él súlya nem negatív ((u, v) ? 0 minden (u) esetén , v) E). Abban az esetben, ha a gráf élei nem egyenlőek, célszerű ezt az algoritmust használni.
Feladat megfogalmazása. Van egy grafikon. Némelyik csúcsa 1. csúcsnak van kijelölve. Meg kell találni a minimális útvonalakat az 1. csúcstól a gráf minden csúcsáig. A minimális útvonal az az útvonal, amelyen az árak minimális összege szerepel. Az ár egy nem negatív szám, amely az él súlya.
Az algoritmus ötlete. Az ötlet a következő nyilvánvaló állításon alapul: Legyen a minimum út a csúcsból a a B csúcshoz. És legyen B csúcs kapcsolódva bizonyos számú i csúcshoz. Jelölje C i a B csúcsból az i csúcsba vezető út költségét. Válasszuk ki a minimális értéket C i-ből. Ekkor a B ponttól induló út minimális folytatása a választott értéken halad át.
Ez az állítás nem igazán igényel bizonyítást. És ebből nagyon súlyos következmény következik. Legyen egy olyan csúcshalmaz, amelyen már minimális utak haladnak át. Egy ilyen halmaz garantáltan létezik, ez az 1. csúcs. A fent megfogalmazott állítás lehetővé teszi, hogy a már meglévő csúcshalmazhoz még egy csúcsot adjunk (a továbbiakban kiválasztottnak nevezzük), és mivel a gráf csúcsainak száma véges, akkor véges számú lépésben kijelöljük a gráf összes csúcsát, és ez lesz a megoldás.
A Dijkstra-algoritmus lényege az az eljárás, amellyel még egy csúcsot adunk a kiválasztottak halmazához. Ez az eljárás két lépésből áll:
1. Felépítjük a kiválasztotthoz beeső csúcsok halmazát, és megkeressük közöttük a legalacsonyabb árú csúcsot. A talált csúcs hozzáadódik a kiválasztottak halmazához.
2. Összeállítunk egy csúcshalmazt a kiválasztotthoz, és meghatározzuk az új árakat. Egy csúcs új ára a kiválasztott csúcsok halmazától az adott csúcsig vezető útvonal minimális költsége. Az új ár a következőképpen épül fel:
a. A kiválasztott csúcsok halmazában lévő nem kiválasztott csúcsok esetében meghatározásra kerül az ehhez tartozó csúcsok egy részhalmaza.
b. A kiválasztott részhalmaz minden csúcsára meghatározásra kerül az adott részhalmazhoz vezető út költsége.
c. A minimális ár kerül meghatározásra. Ez az ár lesz a felső ár.
Az algoritmus kétféle áron működik: szélső áron és felső áron. Az élárak állandóak. A csúcsok árait folyamatosan újraszámolják. Ezeknek az áraknak a jelentése más. Egy él költsége annak a költsége, hogy egy csúcsból egy olyan csúcsba lépünk, amelyet az él köt össze. A csúcs ára pedig a minimum út ára. Egy másik fontos megjegyzés az előzetes árak újraszámítására vonatkozik. Valójában csak azokra a csúcsokra van értelme az előzetes árakat újraszámolni, amelyek az utolsó lépésben a kiválasztottak halmazához hozzáadott csúcshoz kapcsolódnak, mivel más csúcsok esetében nincs ok az előzetes ár megváltoztatására.
Köztudott, hogy minden ár (például egy ösvény vagy átjáró fektetése) nem negatív. Keresse meg a legkisebb költségű 1->i útvonalat minden i=1-re. n O(n2) időben.
Az algoritmus működése során néhány város kiválasztásra kerül (az elején - csak az 1. város, a végén - az összes). Ahol:
minden kiválasztott i városnál az 1->i útvonal legkisebb költségét tároljuk; ugyanakkor ismeretes, hogy a minimumot a csak kiválasztott városokon áthaladó úton érik el;
minden i allokálatlan városhoz az 1->i útvonal legkisebb költségét tároljuk, amelyben csak a kiválasztott városokat használjuk köztesként.
A kiosztott városok halmaza a következő megjegyzés alapján bővül: ha az összes ki nem osztott város közül azt vesszük, amelyiknél minimális a tárolt szám, akkor ez a szám a valódi legkisebb költség. Valóban, legyen rövidebb út. Tekintsük az első ki nem választott várost ezen az úton – a hozzá vezető út már hosszabb! (Itt elengedhetetlen az árak negatívsága.)
Ha a kiválasztott várost hozzáadjuk a kiválasztottakhoz, javítanunk kell a nem kiválasztott városoknál tárolt információkat. Ebben az esetben elegendő csak azokat az utakat figyelembe venni, amelyeken az új város az utolsó átszállási pont, és ez könnyen megtehető, hiszen már ismerjük az új városba vezető út minimális költségét.
Más szavakkal, a V minden csúcsa egy címkével van társítva – ez a minimális ismert távolság ettől a csúcstól a-ig. Az algoritmus lépésről lépésre működik - minden lépésben "meglátogat" egy csúcsot, és megpróbálja csökkenteni a címkéket. Az algoritmus akkor fejeződik be, amikor az összes csúcsot meglátogattuk.
Inicializálás. Felső címke a egyenlőnek kell lennie 0 , a fennmaradó csúcsok címkéi a végtelen. Ez azt a távolságot tükrözi a más csúcsokra még nem ismertek. A gráf minden csúcsa nem látogatottként van megjelölve.
Algoritmus lépés. Ha az összes csúcsot meglátogattuk, az algoritmus leáll. Ellenkező esetben a még meg nem látogatott csúcsok közül kiválasztásra kerül egy csúcs u A minimális címkével. Minden lehetséges útvonalat mérlegelünk, amelyen u az utolsó előtti pont. Csúcshoz kapcsolódó csúcsok uélek, akkor ennek a csúcsnak a szomszédait fogjuk hívni. Minden szomszédnál vegyen egy új útvonalhosszt, amely megegyezik az aktuális címke összegével ués az összekötő él hossza u ezzel a szomszéddal. Ha a kapott hosszúság kisebb, mint a szomszéd címkéje, cserélje ki a címkét erre a hosszúságúra. Az összes szomszédot figyelembe véve megjelöljük a csúcsot u ahogy meglátogatta, és ismételje meg a lépést.
Mivel Dijkstra algoritmusa minden alkalommal úgy dönt, hogy a legrövidebb út legkisebb becslésével rendelkező csúcsot dolgozza fel, azt mondhatjuk, hogy a mohó algoritmusok közé tartozik.
Írjuk le részletesebben, hogyan működik Dijkstra algoritmusa.
Az algoritmus három, egyenként N számból álló tömböt (= hálózati csúcsok száma) használ. Az első A tömb két értékű címkéket tartalmaz: 0 (a csúcs még nincs figyelembe véve) és 1 (a csúcs már figyelembe véve); a második B tömb a távolságokat tartalmazza - az aktuális legrövidebb távolságokat a megfelelő csúcsig; a harmadik c tömb a csúcsok számát tartalmazza - a k-edik C elem [k] az utolsó előtti csúcs száma a Vi-től Vk-ig tartó jelenlegi legrövidebb úton. A D távolságmátrix megadja a D ív hosszát; ha nincs ilyen ív, akkor D-hez egy nagy B számot rendelünk, ami egyenlő a "gép végtelenjével".
Most leírhatjuk:
1. (inicializálás). Egy 1-től N-ig terjedő ciklusban töltse ki az A tömböt nullákkal; töltse ki a C tömböt i számmal; mozgassa a D mátrix i-edik sorát a B tömbbe, A [i]: =1; C [i]: =0 (i - kezdő csúcsszám)
2. (általános lépés). Keresse meg a minimumot a jelöletlenek közül (azaz azok k közül, amelyekre A [k] =0); j indexnél érjük el a minimumot, azaz. B[j]<=B [k] Затем выполняются следующие операции: A [j]: =1; если B [k] >B [j] +D , akkor (B [k]: =B [j] +D ; C [k]: =j) (A feltétel azt jelenti, hogy a Vi. Vk út hosszabb, mint a Vi. Vj Vk út) . (Ha minden A [k] meg van jelölve, akkor a Vi-től Vk-ig tartó út hossza egyenlő B [k]-vel. Most meg kell) felsorolnunk a legrövidebb útba tartozó csúcsokat).
3. (válasz kiadása). (A Vi és Vk útvonalat fordított sorrendben adjuk vissza a következő eljárással:)
2. z kiadás;
3. z:=C[z]. Ha z = 0, akkor vége, ellenkező esetben ugorjon a 3.2-re.
Az algoritmus végrehajtásához az N elemű B tömböt N-szer át kell pásztázni, azaz. Dijkstra algoritmusának négyzetes összetettsége van: O(n2).
Az alábbiakban a Dijkstra-algoritmus blokkvázlata látható (lásd a 2. ábrát).
2. ábra. Dijkstra algoritmusának folyamatábrája
Az algoritmus elején a kezdeti csúcs távolságát nullának tételezzük fel, és az összes többi távolságot nagy pozitív számmal töltjük ki (nagyobb, mint a gráfban lehetséges maximális útvonal). A zászlók tömbje nullákkal van kitöltve. Ezután kezdődik a fő kör.
A hurok minden lépésénél egy olyan csúcsot keresünk, amelynek minimális távolsága és egy nullával egyenlő zászló. Ezután a zászlót 1-re állítjuk benne, és ellenőrizzük a vele szomszédos összes csúcsot. Ha a benne lévő távolság nagyobb, mint az aktuális csúcs távolságának és az él hosszának összege, akkor csökkentjük. A ciklus akkor ér véget, amikor az összes csúcs jelzője 1-gyel egyenlő.
A régió minden városába (ha csak az utakon tud mozogni).
2. lehetőség. A világ városai között számos járat indul, mindegyiknek ismert a költsége. Előfordulhat, hogy egy A-ból B-be tartó járat költsége nem egyezik meg a B-ből A-ba induló járat költségével. Keresse meg a minimális költségű útvonalat (esetleg átszállással) Koppenhágából Barnaulba.
Formális meghatározás
Példa
Tekintsük az algoritmus végrehajtását az ábrán látható gráf példáján!
Meg kell találni a legrövidebb távolságokat az 1. csúcstól az összes többiig.
Megvalósítások programozási nyelveken
Végrehajtás C (C) nyelven
#define SIZE 6 #define INF 1000000000 int a [ SIZE ][ SIZE ] = (( INF , 5 , INF , INF , INF , INF ),( 1 , 2 , 3 , 4 , 5 , 6 ), // útvonalmátrix ( 1 , 2 , 3 , 4 , 5 , 6 ), ( 1 , 2 , 3 , 4 , 5 , 6 ), // vízszintes indexek pontból { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // függőlegesen egy ponthoz, érték - súly int d[ MÉRET ]; // talált legrövidebb utak tömbje, indexek - gráfcsúcsok void deikstra () ( int v [ SIZE ]; // címkék tömbje int temp , i ; int miniindex , min ; for (i = 0 ; i )< SIZE ; i ++ ) { d [ i ] = INF ; // a végtelenig inicializált útvonalak tömbje v[i] = 1; ) d [ 0 ] = 0 ; do( // algoritmus végrehajtása miniindex = INF ; min = INF; for (i = 0 ; i< SIZE ; i ++ ) { if ((v [ i ] == 1 ) && (d [ i ] < min )) { min = d [ i ]; minindex = i ; } } if (minindex != INF ) { for (i = 0 ; i < SIZE ; i ++ ) { if (a [ minindex ][ i ] >0 ) ( temp = min + a [ miniindex ][ i ]; if (hőm< d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }
Adott egy irányított vagy irányítatlan súlyozott gráf csúcsokkal és élekkel. Az összes él súlya nem negatív. Meg van adva néhány kezdőcsúcs. Meg kell találni a csúcstól az összes többi csúcsig tartó legrövidebb utak hosszát, és lehetőséget kell biztosítani maguknak a legrövidebb utak kiadására is.
Ezt a problémát az egyforrású legrövidebb útvonalak problémájának nevezik.
Algoritmus
Ez leírja a holland kutató által javasolt algoritmust Dijkstra(Dijkstra) 1959-ben
Kapjunk egy tömböt, amelyben minden csúcshoz eltároljuk a -tól -ig tartó legrövidebb út aktuális hosszát. Kezdetben és az összes többi csúcsnál ez a hosszúság egyenlő a végtelennel (számítógépen megvalósítva általában elég nagy számot választanak végtelennek, nyilvánvalóan nagyobbat, mint az út lehetséges hossza):
Ezen kívül minden csúcshoz eltároljuk, hogy még feliratozva van-e vagy sem, pl. kapjunk egy logikai tömböt. Kezdetben minden csúcs címkézetlen, azaz.
Dijkstra algoritmusa maga a következőkből áll iterációk. A következő iterációnál a még nem címkézettek közül a legkisebb értékű csúcs kerül kiválasztásra, azaz:
(Egyértelmű, hogy az első iterációnál a kiinduló csúcs kerül kiválasztásra.)
Az így kiválasztott csúcsot jelölve jelöljük. Továbbá az aktuális iterációnál a csúcsból, pihenés: a csúcsból kilépő összes élt átnézik, és minden ilyen csúcsnál az algoritmus megpróbálja javítani az értékét. Legyen az aktuális él hossza , akkor kód formájában a relaxáció így néz ki:
Itt ér véget az aktuális iteráció, az algoritmus továbblép a következő iterációra (ismét a legkisebb értékű csúcsot választjuk ki, abból hajtunk végre relaxációkat stb.). Ebben az esetben a végén az iterációk után a gráf összes csúcsa címkézett lesz, és az algoritmus befejezi a munkáját. Azt állítják, hogy a talált értékek a legrövidebb utak szükséges hosszai -tól -ig.
Érdemes megjegyezni, hogy ha a gráf nem minden csúcsa érhető el a csúcsból, akkor az értékek végtelenek maradnak. Nyilvánvaló, hogy az algoritmus utolsó néhány iterációja csak ezeket a csúcsokat választja ki, de ezek az iterációk nem eredményeznek hasznos munkát (hiszen egy végtelen távolság nem tud lazítani más, még a végtelen távolságokat sem). Ezért az algoritmus azonnal leállítható, amint egy végtelen távolságú csúcsot veszünk kiválasztott csúcsnak.
Út helyreállítása. Természetesen általában nem csak a legrövidebb utak hosszát kell ismerni, hanem magukat az utakat is. Mutassuk meg, hogyan tárolhatunk elegendő információt a legrövidebb út későbbi rekonstrukciójához bármely csúcsig. Ehhez az ún őstömb: egy tömb, amely minden csúcsra tartalmazza annak a csúcsnak a számát, amelyik az utolsó előtti a csúcshoz vezető legrövidebb úton. Ez azt a tényt használja fel, hogy ha a legrövidebb utat választjuk valamelyik csúcshoz, majd eltávolítjuk az utolsó csúcsot ebből az útból, akkor egy olyan utat kapunk, amely valamilyen csúcsban végződik, és ez az út lesz a legrövidebb a vertex számára. Tehát, ha megvan ez az őstömbünk, akkor a legrövidebb út állítható vissza belőle, egyszerűen minden alkalommal, amikor az őst az aktuális csúcsból vesszük, amíg el nem jutunk a kezdő csúcshoz - így megkapjuk a kívánt legrövidebb utat, de beírva fordított sorrendben. Tehát a legrövidebb út a csúcsra:
Továbbra is meg kell értenünk, hogyan építsük fel ezt az őstömböt. Ez azonban nagyon egyszerűen történik: minden egyes sikeres relaxációnál, i.e. amikor a kiválasztott csúcstól valamely csúcs távolsága javul, akkor azt írjuk, hogy a csúcs őse a csúcs:
Bizonyíték
Fő nyilatkozat, amelyen a Dijkstra-féle algoritmus helyessége alapul, a következő. Azt állítják, hogy bármely csúcs megjelölése után az aktuális távolság már a legrövidebb, és ennek megfelelően már nem változik.
Bizonyíték indukcióval fogjuk előállítani. Az első iterációnál az érvényessége nyilvánvaló - a nálunk lévő csúcsra, amely a hozzá vezető legrövidebb út hossza. Most érvényes legyen ez az állítás minden korábbi iterációra, pl. minden már megjelölt csúcs; bizonyítsuk be, hogy az aktuális iteráció végrehajtása után nem sérült. Legyen az aktuális iterációnál kiválasztott csúcs, azaz. az a csúcs, amelyet az algoritmus címkézni fog. Bizonyítsuk be, hogy valóban egyenlő a hozzá vezető legrövidebb út hosszával (ezt a hosszt jelöljük).
Fontolja meg a legrövidebb utat a csúcsra. Nyilvánvaló, hogy ez az út két útra osztható: , amely csak megjelölt csúcsokból áll (legalábbis a kezdő csúcs ebben az útvonalban lesz), és az út többi részére (ez is tartalmazhat jelölt csúcsokat, de mindig elindul jelöletlennel). Jelölje az útvonal első csúcsával , és az útvonal utolsó csúcsával .
Először bizonyítsuk be állításunkat a csúcsra, azaz bizonyítsuk be az egyenlőséget. Ez azonban szinte nyilvánvaló: végül is az egyik előző iterációnál kiválasztottunk egy csúcsot, és abból hajtottunk végre relaxációt. Mivel (a csúcs megválasztásából adódóan) a legrövidebb út egyenlő a legrövidebb út plusz élhez , akkor amikor a relaxációt végrehajtjuk, az érték valóban a kívánt értékre lesz állítva.
Az élek költségeinek nem-negativitása miatt a legrövidebb út hossza (amely az imént bizonyítottak szerint egyenlő ) nem haladja meg a csúcshoz vezető legrövidebb út hosszát. Figyelembe véve, hogy (végül is Dijkstra algoritmusa nem talált rövidebb utat, mint az általában lehetséges), ennek eredményeként a következő összefüggéseket kapjuk:
Másrészt, mivel mind a és és mind címkézetlen csúcsok, mivel az aktuális iterációnál a csúcsot választottuk, nem pedig a csúcsot, egy másik egyenlőtlenséget kapunk:
Ebből a két egyenlőtlenségből következtetjük az egyenlőséget, majd az előbb talált összefüggésekből kapjuk és:
Q.E.D.
Végrehajtás
Tehát a Dijkstra algoritmus iterációkból áll, amelyek mindegyikénél kiválasztunk egy legkisebb értékű címkézetlen csúcsot, ezt a csúcsot felcímkézik, majd átnézik az ebből a csúcsból kilépő összes élt, és minden él mentén megpróbálják javítani a csúcsot. érték az él másik végén.
Az algoritmus futási ideje a következők összege:
Ezen műveletek legegyszerűbb megvalósításával a műveletek egy csúcs megtalálására, a műveletek egy relaxációra és a végső aszimptotikumok az algoritmus:
Végrehajtás:
const int INF = 1000000000 ; int main() ( int n; ... n olvassa ... vektor< vector < pair< int ,int >> > g(n); ... grafikon olvasása... int s = ...; // kezdő csúcs vektor< int >d(n, INF), p(n); d[s] = 0; vektor< char >ENSZ); for (int i= 0 ; i< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }Itt a gráf szomszédsági listák formájában tárolódik: minden csúcshoz a lista tartalmazza az ebből a csúcsból kiinduló élek listáját, azaz. > párok listája, ahol a pár első eleme az a csúcs, amelyhez az él vezet, a második elem pedig az él súlya.
) O(m + n \ln n) idő alatt fut, és ez aszimptotikusan leggyorsabb ismert szekvenciális algoritmus erre a feladatosztályra.
1.2 Az algoritmus matematikai leírása
Legyen adott egy G = (V, E) gráf f(e) élsúlyokkal és egy megkülönböztetett u forráscsúccsal. Jelölje d(v) a legrövidebb távolságot az u forrástól a v csúcsig.
Legyen már kiszámolva minden r távolságot meg nem haladó távolság, vagyis a halmaz csúcsaitól mért távolságok V_r = \( v \in V \mid d(v) \le r \). Hadd
(v, w) \in \arg\min \( d(v) + f(e) \mid v \in V, e = (v, w) \in E \).Akkor d(w) = d(v) + f(e), és v az u-tól w-ig tartó legrövidebb úton fekszik.
Mennyiségek d^+(w) = d(v) + f(e), ahol v \in V_r , e = (v, w) \in E , ún. becsült távolságokés a valós távolságok felső korlátja: d(w) \le d^+(w) .
A Dijkstra algoritmusa minden lépésnél megkeresi a legkisebb becsült távolságú csúcsot, megjelöli látogatottként, és frissíti a becsült távolságokat a belőle kiinduló élek összes végpontjára.
1.3 Az algoritmus számítási magja
A fő számítások a prioritási sorban végzett műveletekhez kapcsolódnak:
- a minimális elem kinyerése (delete_min);
- csökkentse egy elem prioritását (decrease_key).
1.4 Az algoritmus makrostruktúrája
Algoritmus pszeudokód:
Beviteli adat: gráf csúcsokkal V, élek E mérleggel f(e); forrás csomópont u. Kimenet: távolságok d(v) minden csúcsra v ∈ V a tetejéről u. K := új prioritási sor az egyes v ∈ V: ha v = u akkor d(v) := 0 más d(v) := ∞ K.insert( v, d(v)) míg K ≠ ∅: v := K.delete_min() az egyes e = (v, w) ∈ E: ha d(w) > d(v) + f(e): d(w) := d(v) + f(e) K.decrease_key( w, d(w))1.5 Szekvenciális algoritmus megvalósítási séma
A Dijkstra-algoritmus konkrét megvalósítását a használt prioritási soralgoritmus megválasztása határozza meg. A legegyszerűbb esetben ez lehet egy tömb vagy egy lista, ahol a minimum keresése megköveteli az összes csúcs megtekintését. Hatékonyabb a kupac használata; a legismertebb komplexitásbecslés a Fibonacci kupacot használó változatra vonatkozik.
Egy megvalósítási lehetőség akkor lehetséges, ha a csúcsokat nem az inicializálási szakaszban, hanem az első látogatáskor adják hozzá a sorhoz.
1.6 Az algoritmus szekvenciális összetettsége
Az algoritmus szekvenciális összetettsége O(C_1 m + C_2n) , ahol
- C_1 – a csúcstól való távolság csökkentésére szolgáló műveletek száma;
- C_2 a minimum kiszámításához szükséges műveletek száma.
Dijkstra eredeti algoritmusa listákat használt belső adatstruktúraként, amelyeknél C_1 = O(1) , C_2 = O(n) , így a teljes komplexitás O(n^2) volt.
A Fibonacci kupac használatakor a minimális számítási idő C_2 = O(\ln n) értékre csökken, így a teljes komplexitás O(m + n \ln n) , ami aszimptotikusan a legismertebb eredmény erre a feladatosztályra.
1.7 Információs grafikon
Egy algoritmus gráfot adunk meg Dijkstra algoritmusának listákon vagy tömbökön történő alapvető megvalósításához.
1. ábra Algoritmusgrafikon a bemeneti és kimeneti adatok megjelenítése nélkül. n=3. Az összehasonlítási műveletek sárgával, a csúcscímkék megváltoztatásának műveletei zölddel, a csúcscímkézés pedig kékkel vannak jelölve.
1.8 Algoritmus-párhuzamossági erőforrás
Dijkstra algoritmusa hatékony párhuzamosítást tesz lehetővé, átlagos futási idő O(n^(1/3)\ln n) O(n \ln n + m) számítási térfogattal.
Az első becslés a daps karakterisztikán alapul, amely a másodpercenkénti memóriaelérések (olvasás és írás) számát méri. Ez a jellemző analóg a flops becsléssel a memóriával való munkával kapcsolatban, és inkább a memóriával való interakció teljesítményének becslése, mint a lokalitás becslése. Azonban jó információforrásként szolgál, beleértve a következő cvg szolgáltatás eredményeivel való összehasonlítást is.
A 6. ábra a gyakori algoritmusok implementációihoz tartozó daps értékeket mutatja, növekvő sorrendben (minél több daps, annál jobb általában a teljesítmény). Látható, hogy a memória teljesítménye meglehetősen alacsony. Ez nem meglepő, hiszen az algoritmusok gráfokon keresztül történő megvalósítása szinte mindig alacsony hatékonyságú az adatokhoz való hozzáférés szabálytalansága miatt, amit a hozzáférési profil elemzésekor tapasztaltunk.
6. ábra A daps pontszámok összehasonlítása
A második jellemző, a cvg, a géptől függetlenebb lokalitásbecslést szolgálja. Meghatározza, hogy a programnak milyen gyakran kell adatokat behúznia a gyorsítótárba. Ennek megfelelően minél kisebb a cvg érték, minél ritkábban kell ezt megtenni, annál jobb a helység.
A 7. ábra a cvg értékeket mutatja ugyanarra az implementációkészletre, csökkenő sorrendbe rendezve (minél kisebb a cvg, annál magasabb általában a helység). Látható, hogy ebben az esetben a cvg érték jól korrelál a teljesítménypontszámmal és alacsony lokalitást tükröz, ami összhangban van a kvalitatív lokalitásértékelés megállapításaival.
7. ábra A cvg pontszámok összehasonlítása
2.3. Az algoritmus párhuzamos megvalósításának lehetséges módszerei és jellemzői
2.4 Az algoritmus skálázhatósága és megvalósítása
2.4.1 Az algoritmus skálázhatósága
2.4.2 Az algoritmus implementáció skálázhatósága
Vizsgáljuk meg az algoritmus párhuzamos megvalósításának skálázhatóságát a módszertan szerint. A vizsgálatot a Moszkvai Egyetem Szuperszámítógép-komplexumának Lomonoszov szuperszámítógépén végezték. Az algoritmus megvalósításának indításához szükséges változó paraméterek értékkészlete és határai:
- az egész négyzetértékű processzorok száma;
- grafikon mérete 16000 lépéssel.
Az alábbi ábra az algoritmus kiválasztott implementációjának teljesítményét mutatja be a változtatható indítási paraméterek függvényében.
8. ábra Az algoritmus párhuzamos megvalósítása. A teljesítmény változása a processzorok számától és a terület méretétől függően.
Az algoritmus párhuzamos megvalósításának sajátosságai miatt az összteljesítmény meglehetősen alacsony és a folyamatok számának növekedésével lassan növekszik, a 128-as folyamatok számához közeledve pedig csökkenni kezd. Ez azzal magyarázható, hogy az algoritmus minden iterációja során kollektív műveleteket alkalmaznak, és az a tény, hogy a kommunikációs cserék költségei jelentősen megnövekednek a felhasznált folyamatok számának növekedésével. Az egyes folyamatokra vonatkozó számítások meglehetősen gyorsak, ezért a gráffelbontás gyengén kompenzálja a kommunikációs cserék költségeinek hatását.
2.5 Dinamikus teljesítmény és algoritmus implementáció hatékonysága
A kísérletekhez a Dijkstra-algoritmus implementációját használtam. Minden eredményt a Lomonoszov szuperszámítógépen kaptunk. 94 Gflops csúcsteljesítményű Intel Xeon X5570 processzorokat, valamint egy Intel 13.1.0 fordítót használtunk. Az ábrák a Dijkstra-algoritmus megvalósításának hatékonyságát mutatják 32 folyamaton.
9. ábra: CPU terhelési grafikon a Dijkstra algoritmus végrehajtásakor
A processzor terhelési grafikonja azt mutatja, hogy a program szinte teljes futási ideje alatt a terhelési szint körülbelül 50%. Ez a processzorok egyenletes terhelését jelzi, ha számítási csomópontonként 8 folyamatot használ, és Hyper Threading használata nélkül.
10. ábra: Lebegőpontos műveletek másodpercenkénti diagramja Dijkstra algoritmusának végrehajtásakor
A 10. ábra a másodpercenkénti lebegőpontos műveletek grafikonját mutatja. A grafikon összességében nagyon gyenge teljesítményt mutat, körülbelül 250 Kflops csúcson, és körülbelül 150 Kflops átlagosan az összes csomóponton. Ez azt jelzi, hogy a programban szinte minden számítás egész számokkal történik.
A memóriába írás grafikonja a számítási egyenetlenségek hasonló mintáját mutatja, csak néhány folyamat ír aktívan egy időben. Ez korrelál más végrehajtási ütemezésekkel. Érdemes megjegyezni a memória írási hozzáférések meglehetősen alacsony számát. Ez a számítások jó szervezését és a memória meglehetősen hatékony munkáját jelzi.
15. ábra: Az Infiniband hálózaton keresztüli átviteli sebesség grafikonja bájt/mp-ben, amikor a Dijkstra algoritmus fut
Az Infiniband hálózati adatátviteli sebesség grafikonján meglehetősen magas adatátviteli sebesség látható bájt per másodpercben. Ez azt sugallja, hogy a folyamatok intenzíven és valószínűleg meglehetősen kis mennyiségű adatot cserélnek egymással, mivel a számítási teljesítmény magas. Érdemes megjegyezni, hogy az átviteli sebesség folyamatonként eltérő, ami számítási egyensúlyhiányra utal.
16. ábra: Az Infiniband hálózaton keresztüli átviteli sebesség grafikonja csomagokban / másodpercben, amikor a Dijkstra algoritmus fut
A másodpercenkénti csomagokban kifejezett adatátviteli sebesség grafikonján rendkívül nagy adatátviteli intenzitás látható. Ez arra utal, hogy a folyamatok valószínűleg nem túl jelentős mennyiségű adatot cserélnek, de nagyon intenzíven. Az egyes lépésekben kollektív műveleteket használnak kis adatrészletekkel, ami megmagyarázza ezt a képet. A folyamatok között kisebb az egyensúlyhiány, mint a memóriahasználati, számítási és adatátviteli bájt/s grafikonon. Ez azt jelzi, hogy a folyamatok az algoritmus szerint ugyanannyi csomagot cserélnek, de eltérő mennyiségű adatot kapnak, és egyenetlen számításokat végeznek.
17. ábra A számlálási szakaszba (Loadavg) várakozó folyamatok számának grafikonja, amikor a Dijkstra algoritmus fut
A számlálási szakaszba (Loadavg) belépésre váró folyamatok számának grafikonja azt mutatja, hogy ennek a paraméternek az értéke a program teljes működése alatt állandó, és megközelítőleg 8. Ez a program stabil működését jelzi minden betöltött számítással. csomópontok. Ez a hardver erőforrások folyamatok általi nagyon racionális és statikus terhelését jelzi. És az elvégzett megvalósítás meglehetősen jó hatékonyságát mutatja. Általánosságban elmondható, hogy a program rendszerfigyelése alapján megállapítható, hogy a program meglehetősen hatékonyan és stabilan működött. A memóriahasználat rendkívül intenzív, a kommunikációs médiahasználat pedig rendkívül intenzív, az adatátviteli volumen pedig nem magas. Ez jelzi a program algoritmikus részének kommunikációs környezete késleltetésének szigorú jellegét. Úgy tűnik, hogy az alacsony hatásfok az egyes folyamatok meglehetősen magas átviteli mennyiségével és intenzív üzenetváltással jár.