Deykstra algoritmidan foydalanib eng qisqa yo'lni topish masalasini yeching.
X0 dan X7 gacha bo'lgan eng qisqa yo'lni toping. Grafik xarajatlar matritsasi elementlari bilan berilgan
Keling, ushbu grafikni tuzamiz 
X0 elementidan boshlaylik va unga 0 belgisini belgilaymiz, chunki uning barcha qo'shnilarini ko'rib chiqing hali hech qanday belgilar yo'q, keyin biz ularga tegishli uzunliklarni tayinlaymiz: 
Barcha qo'shnilar X0 hisobga olinadi, biz uni belgilaymiz va X1 tepasiga o'tamiz. Uning qo'shnilari X0, X2, X4, lekin X0 belgilangan, biz buni hisobga olmaymiz. X2 uchun: 
, yorliqni qoldiring.
X4 uchun: 
, yorliqni almashtiring. X1 vertexning barcha qo'shnilari hisobga olinadi, biz uni belgilaymiz 
yuqori X2 ga o'ting. Uning qo'shnilari X0, X1, X3, X4, X5, X6, lekin X0, X1 belgilangan, biz ularni hisobga olmaymiz.
X3 uchun: 
, yorliqni qoldiring.
X5 uchun: 
, yorliqni almashtiring.
X4 uchun: 
, yorliqni qoldiring.
X6 uchun: 
, yorliqni almashtiring.
X2 vertexining barcha qo'shnilari ko'rib chiqildi, biz uni belgilaymiz. 
yuqori X3 ga o'ting. Uning qo'shnilari X0, X2, X6, lekin X0, X2 belgilangan, biz ularni hisobga olmaymiz.
X6 uchun: 
, yorliqni qoldiring.
X3 vertexining barcha qo'shnilari ko'rib chiqildi, biz uni belgilaymiz. 
yuqori X4 ga o'ting. Uning qo'shnilari X1, X2, X5, X7, lekin X1, X2 belgilangan, biz ularni hisobga olmaymiz.
X5 uchun: 
, yorliqni almashtiring.
X7 uchun: 
, yorliqni almashtiring.
X4 vertexining barcha qo'shnilari ko'rib chiqildi, biz uni belgilaymiz. 
yuqori X5 ga o'ting. Uning qo'shnilari X2, X4, X6, X7, lekin X2, X4 belgilangan, biz ularni hisobga olmaymiz.
X6 uchun: 
, yorliqni qoldiring.
X7 uchun: 
, yorliqni qoldiring.
X5 vertexining barcha qo'shnilari ko'rib chiqildi, biz uni belgilaymiz. 
yuqori X6 ga o'ting. Uning qo'shnilari X2, X3, X5, X7, lekin X2, X3, X5 belgilangan, biz ularni hisobga olmaymiz.
X7 uchun: 
, yorliqni qoldiring.
X6 vertexining barcha qo'shnilari ko'rib chiqildi, biz uni belgilaymiz. Va qolgan X7 ni belgilaymiz, barcha tepaliklar hisobga olinadi. 
Xulosa: X0 dan X7 gacha bo'lgan eng qisqa yo'lning uzunligi 101 ga teng, bu yo'l: X7-X4-X1-X0.
Eng qisqa yo'lni topish misolini ko'rib chiqing. Shahar hududlarini bog'laydigan avtomobil yo'llari tarmog'i berilgan. Ba'zi yo'llar bir tomonlama. Shahar markazidan mintaqadagi har bir shaharga eng qisqa yo'llarni toping.
Ushbu muammoni hal qilish uchun siz foydalanishingiz mumkin Dijkstra algoritmi- 1959 yilda golland olimi E. Deykstroy tomonidan ixtiro qilingan grafiklar bo'yicha algoritm. Grafikning bir cho'qqisidan qolgan barcha nuqtalarigacha bo'lgan eng qisqa masofani topadi. Faqat manfiy og'irlikdagi qirralari bo'lmagan grafiklar uchun ishlaydi.
1-cho'qqidan qolgan barcha nuqtalargacha bo'lgan eng qisqa masofalarni topish talab qilinsin.
Doiralar cho'qqilarni, chiziqlar ular orasidagi yo'llarni (grafikning qirralarini) ko'rsatadi. Doiralar cho'qqilarning raqamlarini ko'rsatadi, qirralarning tepasida ularning og'irligi - yo'lning uzunligi ko'rsatilgan. Har bir cho'qqi yonida qizil yorliq mavjud - bu cho'qqiga 1-cho'qqigacha bo'lgan eng qisqa yo'lning uzunligi.
1 cho'qqisining yorlig'i o'zi 0 ga teng, qolgan cho'qqilarning teglari etib bo'lmaydigan raqam (ideal, cheksizlik). Bu 1-cho'qqidan boshqa cho'qqilargacha bo'lgan masofalar hali ma'lum emasligini aks ettiradi. Grafikning barcha cho'qqilari ko'rilmagan deb belgilangan. 
Birinchi qadam
1-cho'qqi minimal yorlig'iga ega.Uning qo'shnilari 2,3 va 6 cho'qqilardir.Biz cho'qqining qo'shnilarini navbat bilan aylanib chiqamiz.
1-cho'qqining birinchi qo'shnisi 2-cho'qqidir, chunki unga boradigan yo'l uzunligi minimaldir. 1-cho'qqi orqali unga boradigan yo'lning uzunligi 1-cho'qqigacha bo'lgan eng qisqa masofa, uning yorlig'i qiymati va 1-dan 2-gacha bo'lgan chekka uzunligi yig'indisiga teng, ya'ni 0 + 7 = 7. Bu 2-cho'qqining joriy yorlig'idan (10000) kamroq, shuning uchun 2-cho'qqining yangi yorlig'i 7 ga teng. 
Xuddi shunday, biz boshqa barcha qo'shnilar uchun yo'l uzunligini topamiz (3 va 6 cho'qqilar).
1-vertexning barcha qo'shnilari tekshiriladi. 1-cho'qqigacha bo'lgan joriy minimal masofa yakuniy hisoblanadi va qayta ko'rib chiqilmaydi. 1-cho'qqi tashrif buyurilgan deb belgilangan.
Ikkinchi qadam
Algoritmning 1-bosqichi takrorlanadi. Ko'rilmagan cho'qqilarning "eng yaqinini" yana toping. Bu 7 deb belgilangan cho'qqi 2.
Biz yana tanlangan cho'qqining qo'shnilarining teglarini kamaytirishga harakat qilamiz, ular orqali 2-cho'qqi orqali o'tishga harakat qilamiz. 2-cho'qqining qo'shnilari 1, 3 va 4 cho'qqilaridir.
Vertex 1 allaqachon tashrif buyurilgan. 2-cho'qqining keyingi qo'shnisi 3-vertexdir, chunki u tashrif buyurilmagan deb belgilangan cho'qqilarning minimal yorlig'iga ega. Agar siz unga 2 orqali o'tsangiz, unda bunday yo'lning uzunligi 17 ga teng bo'ladi (7 + 10 = 17). Ammo uchinchi cho'qqining joriy yorlig'i 9 va 9 ni tashkil qiladi< 17, поэтому метка не меняется.
2-cho'qqining yana bir qo'shnisi - 4-vertex. Agar siz unga 2-chi orqali o'tsangiz, bunday yo'lning uzunligi 22 ga teng bo'ladi (7 + 15 = 22). 22 dan beri<10000, устанавливаем метку вершины 4 равной 22.
2-vertexning barcha qo'shnilari ko'rib chiqildi, biz uni tashrif buyurilgan deb belgilaymiz.
Uchinchi qadam
Algoritmning qadamini 3-vertexni tanlab takrorlaymiz.Uni “qayta ishlash”dan keyin quyidagi natijalarga erishamiz. 
To'rtinchi qadam
Beshinchi qadam
Oltinchi qadam
Shunday qilib, 1-cho'qqidan 5-cho'qqigacha bo'lgan eng qisqa yo'l cho'qqilar orqali o'tadigan yo'l bo'ladi 1 — 3 — 6 — 5
chunki bu yo'l bilan biz 20 minimal vaznga ega bo'lamiz.
Keling, eng qisqa yo'lning hosilasini ko'rib chiqaylik. Biz har bir cho'qqi uchun yo'lning uzunligini bilamiz va endi biz uchlarini oxiridan boshlab ko'rib chiqamiz. Yakuniy cho'qqini ko'rib chiqing (bu holda, cho'qqi 5
) va u bogʻlangan barcha choʻqqilar uchun oxirgi choʻqqining yoʻl uzunligidan mos keladigan chetning ogʻirligini ayirib, yoʻl uzunligini topamiz.
Shunday qilib, yuqori 5
yo'l uzunligi bor 20
... U cho'qqilarga bog'langan 6
va 4
.
Yuqori uchun 6
vaznni oling 20 - 9 = 11 (mos keladi).
Yuqori uchun 4
vaznni oling 20 - 6 = 14 (mos kelmadi).
Agar natijada biz ko'rib chiqilayotgan cho'qqining yo'l uzunligiga to'g'ri keladigan qiymatni olsak (bu holda, cho'qqi 6
), keyin aynan shu nuqtadan yakuniy cho'qqiga o'tish amalga oshirildi. Biz bu cho'qqini kerakli yo'lda belgilaymiz.
Keyinchalik, biz cho'qqiga chiqadigan chetni aniqlaymiz 6
... Va shunga o'xshash, biz boshiga yetguncha.
Agar bunday o'tish natijasida bir necha bosqichda biz bir nechta cho'qqilar uchun bir xil qiymatlarga ega bo'lsak, biz ulardan istalganini olishimiz mumkin - bir nechta yo'llar bir xil uzunlikka ega bo'ladi.
Dijkstra algoritmini amalga oshirish
Grafik og'irliklarini saqlash uchun kvadrat matritsa ishlatiladi. Qator va ustunlar sarlavhalari grafikning uchlarini o'z ichiga oladi. Grafik yoylarining og'irliklari esa jadvalning ichki kataklariga joylashtirilgan. Grafikda halqalar mavjud emas, shuning uchun matritsaning asosiy diagonali nol qiymatlarni o'z ichiga oladi.
| 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 |
C ++ dasturini amalga oshirish
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
#aniqlang _CRT_XAVFSIZ_OGOHLANTIRISH
#o'z ichiga oladi
#o'z ichiga oladi
#6 oʻlchamini aniqlang
int main ()
{
int a; // havolalar matritsasi
int d; // minimal masofa
int v; // tashrif buyurilgan cho'qqilar
int temp, minindex, min;
int begin_index = 0;
tizim ("chcp 1251");
tizim ("cls");
// Havolalar matritsasini ishga tushiring
uchun (int i = 0; i
a [i] [i] = 0;
uchun (int j = i + 1; j
scanf ("% d", & temp);
a [i] [j] = temp;
a [j] [i] = temp;
}
}
// Havolalar matritsasini ko'rsatish
uchun (int i = 0; i
uchun (int j = 0; j
printf ("\ n");
}
// Cho'qqilar va masofalarni ishga tushiring
uchun (int i = 0; i
d [i] = 10000;
v [i] = 1;
}
d = 0;
// Algoritm bosqichi
qilmoq (
minindex = 10000;
min = 10000;
uchun (int i = 0; i
agar ((v [i] == 1) && (d [i]
min = d [i];
minindex = i;
}
}
// Topilgan minimal vaznni qo'shing
// cho'qqining joriy og'irligiga
// va cho'qqining joriy minimal og'irligi bilan solishtiring
agar (minindex! = 10000)
{
uchun (int i = 0; i
agar (a [i]> 0)
{
temp = min + a [i];
agar (harorat< d[i])
{
d [i] = harorat;
}
}
}
v = 0;
}
) while (minindex< 10000);
// Cho'qqilargacha bo'lgan eng qisqa masofalarni ko'rsatish
printf ( "\ nToʻqqilarga eng qisqa masofalar: \ n");
uchun (int i = 0; i
// Yo'lni tiklang
int ver; // tashrif buyurilgan cho'qqilar massivi
int end = 4; // yakuniy cho'qqi indeksi = 5 - 1
ver = end + 1; // boshlang'ich element - tugatish cho'qqisi
int k = 1; // oldingi uchining indeksi
int og'irligi = d; // oxirgi uchining og'irligi
esa (oxiri! = start_index) // hali boshlang'ich cho'qqiga etib bormagan
{
uchun (int i = 0; i
agar (a [i]! = 0) // agar ulanish mavjud bo'lsa
{
int temp = og'irlik - a [i]; // oldingi cho'qqidan yo'lning og'irligini aniqlang
agar (harorat == d [i]) // agar vazn hisoblanganga to'g'ri kelsa
{ // bu cho'qqidan o'tish sodir bo'lganligini bildiradi
vazn = harorat; // yangi vaznni saqlang
oxiri = i; // oldingi uchini saqlang
ver [k] = i + 1; // va uni massivga yozing
k ++;
}
}
}
// Yo'lni chiqaring (boshlang'ich uchi k elementli massivning oxirida edi)
printf ( "\ nEng qisqa yo'lni ko'rsatish \ n");
uchun (int i = k - 1; i> = 0; i--)
printf ("% 3d", versiya [i]);
getchar (); getchar ();
qaytish 0;
}
Amalga oshirish natijasi
Orqaga:
Dijkstra algoritmi yo'naltirilmagan grafikdagi cho'qqilar orasidagi eng qisqa yo'lni topishga mo'ljallangan.
Algoritmning g'oyasi quyidagicha: birinchi navbatda, nolga teng bo'lgan boshlang'ich cho'qqigacha bo'lgan yo'lni tanlaymiz va bu cho'qqini allaqachon tanlanganlar to'plamiga qo'shamiz, qolgan tanlanmagan cho'qqilargacha bo'lgan masofa aniqlanadi. Har bir keyingi bosqichda biz keyingi tanlangan cho'qqini topamiz, uning masofasi eng kichik va tanlanmaganlar to'plamidan biron bir cho'qqiga chekka bilan bog'langan (bu masofa tanlangan cho'qqigacha bo'lgan masofaga va uzunligiga teng bo'ladi). chetidan).
1-misol. Grafikdagi eng qisqa yo'lni tepadan toping L tepaga D(10.7-rasm).
Guruch. 10.7.
Algoritmni bosqichlar ketma-ketligi shaklida yozamiz (10.1-jadval). Qadam 1. Boshlang'ich cho'qqigacha bo'lgan masofani aniqlang L hammadan oldin.
10.1-jadval
Dijkstra usuli (birinchi qadam)
|
Tanlangan |
Tanlangan cho'qqiga yo'l |
Tanlanmagan cho'qqi |
|||||||
Qadam 2. dan eng kichik masofani tanlang L oldin V; cho'qqisi topildi V yangi tanlangan sifatida qabul qilinadi. Topilgan eng kichik masofa yangi tepadan qirralarning uzunliklariga qo'shiladi V hammadan oldin. Biz minimal masofani tanlaymiz V oldin N. Yangi cho'qqi N biz tanlanganni olamiz (10.2-jadval).
10.2-jadval
Deykstra usuli (ikkinchi bosqich)
|
Tanlangan |
Tanlangan cho'qqiga yo'l |
Tanlanmagan cho'qqi |
|||||||
Aniqlik uchun, keyingi gaplarda oo belgisi o'rniga "-" belgisini qo'yamiz.
Qadam 3. Yuqoridan masofani aniqlang N l qolganlari haqida (shundan tashqari L va V), jadvalda ko'rsatilganidek. 10.3.
10.3-jadval
Dijkstra usuli (uchinchi bosqich)
|
Tanlangan |
Tanlangan cho'qqiga yo'l |
Tanlanmagan cho'qqi |
|||||||
Tepadan masofa L tepa bo'ylab N uchun tepalar G 18 ta shartli birlikka teng. Bu masofa masofadan kattaroqdir LB + BG= 16 an'anaviy birlik, buning natijasida kelajakda hisobga olinmaydi. Shunga o'xshash konstruktsiyalarni davom ettirib, biz jadval tuzamiz. 10.4. Shunday qilib, cho'qqilar orasidagi eng qisqa yo'lning uzunligi topildi L va D(44 an'anaviy birlik).
Yo'lning traektoriyasi quyidagicha aniqlanadi. Biz oxirgi cho'qqidan boshlang'ich nuqtaga teskari qidiruvni amalga oshiramiz. Biz yuqoridan yuqoriga mos keladigan ustunni ko'rib chiqamiz va minimal qiymatning birinchi paydo bo'lishini aniqlaymiz. Tepaga mos keladigan ustunda D, birinchi marta to'rtinchi qatorda pastki qismida 44 ta an'anaviy birlikning minimal uzunligi paydo bo'ldi. Bu chiziq cho'qqini ko'rsatadi S, qaysi biri borishi kerak, ya'ni. keyin biz tepaga mos keladigan ustunni ko'rib chiqishimiz kerak S.
10.4-jadval
|
Tanlangan cho'qqi |
Tanlangan cho'qqiga yo'l |
Tanlanmagan cho'qqi |
|||||||
Ushbu ustunda minimal uzunligi 27 an'anaviy birlik keyingi cho'qqini ko'rsatadi G, qaysi biri borishi kerak va hokazo. Shunday qilib, biz yo'lning traektoriyasini olamiz: (L, B, G, S, D).
8-misol. Grafikda 1 va 7 cho'qqilar orasidagi eng qisqa yo'lni toping (10.8-rasm).
Keyingi tanlangan cho'qqini aniqlang (10.5-jadval) masofasi eng kichik bo'lgan va tanlanmaganlar to'plamiga tegishli cho'qqilardan biriga chekka bilan bog'langan (bu masofa tanlangan cho'qqigacha bo'lgan masofaga va uzunligiga teng bo'ladi) chetidan).
Guruch. 10.8. Grafik (a) va mos keladigan qo'shnilik matritsasi (b)
Deykstra usulini jadval shaklida amalga oshirish
10.5-jadval
|
Tanlangan |
Tanlangan cho'qqiga yo'l |
Tanlanmagan cho'qqi |
||||||
|
6 da |
||||||||
Biz oxirgi cho'qqidan boshlang'ich nuqtaga teskari qidiruvni amalga oshiramiz.
Biz yuqoridan yuqoriga mos keladigan ustunni ko'rib chiqamiz va minimal qiymatning birinchi paydo bo'lishini aniqlaymiz. Bu holda eng qisqa yo'l teng bo'ladi (V 7 - V 5 - V 2 - Y ().
va NAZORAT SAVOLLARI
- 1. Algoritmlarning nazariy murakkabligi nimada: qarorlar daraxtini qurish, dinamik dasturlash va Dijkstra?
- 2. Yo'naltirilgan va yo'naltirilmagan grafiklar uchun qarorlar daraxtidan foydalanishning o'ziga xos xususiyati nimada?
- 3. Grafikda berilgan cho’qqilar orasidagi eng qisqa masofalarni aniqlash algoritmlari qanday amaliy masalalarni yechishda qo’llaniladi?
- 4. Ishda ko'rib chiqilgan Deykstra algoritmini yo'naltirilgan grafikdagi eng qisqa masofani aniqlashda qo'llash mumkinmi?
- 5. Deykstra algoritmi qanday ishlaydi?
- 6. Grafikdagi cho’qqilar orasidagi eng qisqa masofalarni aniqlash masalasiga nisbatan dinamik dasturlash algoritmi qanday ishlaydi?
Dijkstra algoritmi - manfiy bo'lmagan yoy uzunliklariga ega bo'lgan grafikdagi ikkita berilgan cho'qqilar orasidagi eng qisqa yo'lni topadigan grafik algoritmi. Bundan tashqari, ko'pincha berilgan cho'qqidan qolgan barcha nuqtalarga eng qisqa yo'lni hisoblash vazifasi qo'yiladi. Algoritm dasturlashda keng qo'llaniladi, masalan, marshrutlash protokollari tomonidan qo'llaniladi.
Tavsif
Algoritmning kiritilishi manfiy bo'lmagan og'irlikdagi yoylarga ega bo'lgan vaznli yo'naltirilgan grafikdir. Chiqish bu cho'qqidan boshqalarga eng qisqa yo'llar to'plamidir.
Dastlab, boshlang'ich cho'qqi uchun masofa nolga teng, qolganlarigacha bo'lgan masofalar esa cheksiz deb qabul qilinadi. Cho'qqidan o'tganligini ko'rsatadigan bayroqlar massivi nol bilan to'ldirilgan. Keyin, tsiklning har bir bosqichida boshlang'ichgacha minimal masofa va nolga teng bayroq bilan cho'qqi qidiriladi. Buning uchun bayroq o'rnatiladi va barcha qo'shni cho'qqilar tekshiriladi. Agar dastlabki cho'qqidan tekshirilgan cho'qqigacha bo'lgan oldindan hisoblangan masofa joriy cho'qqigacha bo'lgan masofa va undan belgilangan cho'qqigacha bo'lgan chekka uzunligi yig'indisidan katta bo'lsa, u holda tekshirilgan cho'qqigacha bo'lgan masofa masofaga tenglashtiriladi. joriy + chekka oqimdan tekshirilgan cho'qqigacha. Barcha cho'qqilarning bayroqlari 1 ga teng bo'lganda yoki bayroq 0 bo'lgan barcha cho'qqilarga masofa cheksiz bo'lganda tsikl tugaydi. Oxirgi holat, agar grafik uzilgan bo'lsa, mumkin.
Dijkstra algoritmi psevdokodda
Kirish: BILAN: real massiv - grafik yoylari uzunliklari matritsasi; s - eng qisqa yo'l izlanadigan cho'qqi va t - izlanadigan cho'qqi.
Chiqish: vektorlar T: real massiv; va H: 0...r massivi. Agar tepada v dan eng qisqa yo'lda yotadi s Kimga t, keyin T [v]- dan eng qisqa yo'l uzunligi s Kimga y; Xo'sh] - darhol oldingi cho'qqi da eng qisqa yo'lda.
H - n cho'qqisi m cho'qqisiga to'g'ri keladigan massiv, s dan n gacha bo'lgan yo'lda oldingi.
T - n tepasi undan s gacha bo'lgan masofaga mos keladigan massiv.
X massiv bo'lib, unda n cho'qqisi unga boradigan yo'l ma'lum bo'lsa 1 ga, bo'lmasa 0 ga to'g'ri keladi.
massivlarni ishga tushirish:
uchun v 1 dan R qil
T[v]: = ∞ (eng qisqa yo'l noma'lum)
X [v]: = 0 (barcha uchlari belgilanmagan)
H [s]: = 0 ( s oldin hech narsa kelmaydi)
T [s]: = 0 (eng qisqa yo'l uzunligi 0 ...)
X [s]: = 1 (... va ma'lum) v : = s (hozirgi cho'qqi)
M: (yangilash qaydlari)
uchun va ∈ G( va) qiling
agar X [va] = 0 & T [va]> T [v] + C keyin
T [u]: = T [v] + C(dan qisqaroq yo'l topildi s v va bo'ylab v }
H [u]:= v(eslab qoling)
m: = ∞
v : = 0
(eng qisqa yo'lning oxirini topish)
uchun va 1 dan p qil
agar X [u] = 0 & T [u]< t keyin
v:= u;
m:= T [u](yuqori v dan eng qisqa yo'lni tugatadi s
agar v = keyin 0
to'xtatish (yo'l yo'q s v t) agar tugaydi
agar v= t keyin
to'xtatish (eng qisqa yo'l topildi s v t) agar tugaydi
X [v]: = 1 (dan eng qisqa yo'l s v v ) borish M
Asoslash
Dijkstra algoritmining to'g'riligini isbotlash uchun shuni ta'kidlash kifoya qiladiki, M belgisi bilan boshlanadigan tsikl tanasining har bir bajarilishi uchun v cho'qqidan eng qisqa yo'l ma'lum bo'lgan cho'qqi ishlatiladi s. Boshqacha qilib aytganda, agar X [v] = 1, u holda T [v] = d (s, v) , va H vektori bilan aniqlangan yo'lda (s, v) barcha uchlari bir xil xususiyatga ega, ya'ni
Vu T [u] = 1 => T [u] = d (s, u) & T] = 1.
Haqiqatan ham (induksiya bo'yicha), birinchi marta sifatida v eng qisqa yo'li bo'sh va uzunligi 0 bo'lgan s cho'qqisi ishlatiladi (bo'sh bo'lmagan yo'llar qisqaroq bo'lishi mumkin emas, chunki yoylarning uzunliklari manfiy emas). T [u] = d (s, u) bo'lsin. oldindan belgilangan barcha uchlari uchun va. Yangi belgilangan tepalikni ko'rib chiqing v, bu T [v] = min T [u] shartidan tanlanadi. E'tibor bering, agar belgilangan cho'qqilardan o'tadigan yo'l ma'lum bo'lsa, u holda eng qisqa yo'l ma'lum bo'ladi. Faraz qilaylik (qarama-qarshilik bilan) T [v]> d (s, v), ya'ni topilgan yo'l dan olib boruvchi. s v v, eng qisqasi emas. Keyin bu yo'lda belgilanmagan cho'qqilar bo'lishi kerak. Birinchi cho'qqini ko'rib chiqing w bu yo'lda T [w] = 0.Bizda: T [w] = d (s, g) ⩽d (s> v)< Т[v],что противоречит выбору вершины u.
Vaqtning murakkabligi
Dijkstra algoritmining murakkabligi ko'rilmagan cho'qqini asl cho'qqigacha minimal masofa bilan topish usuliga, ko'rilmagan cho'qqilar to'plamini saqlash usuliga va teglarni yangilash usuliga bog'liq. Grafikning uchlari soni n, m dan keyin esa qirralarning soni bo'lsin. Keyin, eng oddiy holatda, boshlang'ich cho'qqigacha minimal masofaga ega bo'lgan cho'qqini qidirish uchun butun cho'qqilar to'plami ko'rib chiqilsa va masofalarni saqlash uchun massiv ishlatilsa, algoritmning ishlash vaqti O (n) ga teng. 2). Asosiy sikl taxminan n marta bajariladi, ularning har birida minimalni topish uchun n ga yaqin amallar sarflanadi. Qirralarning soniga mutanosib bo'lgan operatsiyalar soni m (chunki har bir chekka ushbu tsikllarda ikki marta sodir bo'ladi va doimiy son operatsiyalarni talab qiladi) har bir tashrif buyurilgan cho'qqining qo'shnilari bo'ylab halqalarga sarflanadi. Shunday qilib, algoritmning umumiy ishlash vaqti O (n 2 + m), lekin m n (n-1) dan ancha kichik bo'lgani uchun, oxirida biz O (n 2) ni olamiz.
Noyob grafiklar uchun (ya'ni, m n² dan ancha kichik bo'lganlar uchun) ko'rilmagan cho'qqilarni ikkilik to'plamda saqlash mumkin va masofa qiymatlari kalit sifatida ishlatilishi mumkin. Tsikl n martalik tartibda bajarilganligi va bo'shashishlar soni (yorliqlarning o'zgarishi) m dan ortiq bo'lmaganligi sababli, bunday amalga oshirishning ishlash vaqti O (nlogn + mlogn) ga teng.
Misol
1-cho'qqigacha bo'lgan masofani bosib o'tiladigan cho'qqilar bo'yicha hisoblash:
Eng qisqa yo'l grafik deb ataladigan ba'zi bir matematik ob'ekt yordamida ko'rib chiqiladi. Qidirmoq eng qisqa yo'l grafikdagi ikkita berilgan cho'qqi o'rtasida olib boriladi. Natijada yo'l, ya'ni ikkita qo'shni cho'qqiga tushadigan cho'qqilar va qirralarning ketma-ketligi va uning uzunligi.
Eng uchtasini ko'rib chiqing samarali algoritm topish eng qisqa yo'l:
- Dijkstra algoritmi;
- Floyd algoritmi;
- ro'yxatga olish algoritmlari.
Ko'rsatilgan algoritmlar grafikdagi oz sonli uchlari bilan osongina bajariladi. Ularning sonining ko'payishi bilan qidiruv vazifasi eng qisqa yo'l murakkablashadi.
Dijkstra algoritmi
Bu algoritm grafiklar boʻyicha algoritm boʻlib, uni 1959-yilda golland olimi E.Dijkstroy ixtiro qilgan. Algoritm grafikning bir cho'qqisidan qolgan barcha nuqtalarigacha bo'lgan eng qisqa masofani topadi va faqat manfiy og'irlikdagi qirralari bo'lmagan grafiklar uchun ishlaydi.
Har bir cho'qqiga og'irlik beriladi - bu boshlang'ich cho'qqidan berilgangacha bo'lgan yo'lning og'irligi. Bundan tashqari, har bir cho'qqi tanlanishi mumkin. Agar cho'qqi tanlangan bo'lsa, undan boshlang'ich cho'qqigacha bo'lgan yo'l eng qisqasi, agar bo'lmasa, u vaqtinchalik. Grafikni aylanib o'tib, algoritm har bir cho'qqi uchun marshrutni hisoblab chiqadi va agar u eng qisqa bo'lib chiqsa, cho'qqini tanlaydi. Ushbu cho'qqining og'irligi yo'lning og'irligiga aylanadi. Berilgan cho'qqining barcha qo'shnilari uchun algoritm og'irlikni ham hisoblab chiqadi, shu bilan birga ularni hech qanday sharoitda ta'kidlamaydi. Algoritm o'z ishini yakunlaydi, yakuniy cho'qqiga etadi va tortishadi eng qisqa yo'l oxirgi cho'qqining og'irligiga aylanadi.
Dijkstra algoritmi
Qadam 1. Birinchisidan tashqari barcha cho'qqilarga cheksizlikka teng og'irlik, birinchi cho'qqiga esa 0 ga teng bo'ladi.
Qadam 2. Barcha uchlari tanlanmagan.
Qadam 3. Birinchi tepalik oqim deb e'lon qilinadi.
4-qadam. Barcha tanlanmagan cho'qqilarning og'irligi formula bo'yicha qayta hisoblab chiqiladi: tanlanmagan cho'qqining og'irligi - bu cho'qqining eski og'irligidan minimal son, joriy cho'qqi og'irligi yig'indisi va chekka og'irligi. joriy cho'qqini tanlanmagan bilan bog'lash.
Qadam 5. Tanlanmagan cho'qqilar orasidan minimal og'irlikdagi cho'qqi qidiriladi. Agar bittasi topilmasa, ya'ni barcha cho'qqilarning og'irligi cheksizlikka teng bo'lsa, unda marshrut mavjud emas. Demak, chiqish yo'li. Aks holda, topilgan cho'qqi joriy bo'ladi. U ajralib turadi.
Qadam 6. Agar joriy cho'qqi oxirgi bo'lsa, unda yo'l topiladi va uning og'irligi oxirgi cho'qqining og'irligidir.
7-qadam. 4-bosqichga o'ting.
Dasturiy ta'minotni amalga oshirishda Dijkstra algoritmi boshlang'ich cho'qqidan eng qisqa yo'llar allaqachon ma'lum bo'lgan S cho'qqilar to'plamini tuzamiz. Har bir qadamda qolgan cho'qqilardan biri S to'plamga qo'shiladi, boshlang'ich cho'qqigacha bo'lgan masofa qolgan cho'qqilarga qaraganda kamroq. Bunda D massividan foydalanamiz, unda uzunliklar yoziladi eng qisqa yo'llar har bir tepalik uchun. Agar S to'plamda grafikning barcha uchlari bo'lsa, D massivida uzunliklar bo'ladi eng qisqa yo'llar boshlang'ich cho'qqidan har bir cho'qqigacha.
Yuqoridagi massivlarga qo'shimcha ravishda C uzunlikdagi matritsadan foydalanamiz, bu erda C elementi chetning uzunligi (i, j), agar chekka bo'lmasa, uning uzunligi cheksizlikka teng deb qabul qilinadi, bu qirralarning har qanday haqiqiy uzunligidan kattaroqdir. Aslida, C matritsasi qo'shnilik matritsasi, unda barcha nol elementlar cheksizlik bilan almashtiriladi.
Juda aniq aniqlash uchun