Internet va axborot kommunikatsiyasi fakulteti

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.