Dijkstra'nın algoritması, negatif olmayan yay uzunluklarına sahip bir grafikte verilen iki köşe arasındaki en kısa yolu bulan bir grafik algoritmasıdır. Ayrıca, belirli bir tepe noktasından diğerlerine kadar olan en kısa yolu hesaplama görevi sıklıkla ortaya konur. Algoritma programlamada yaygın olarak kullanılır, örneğin yönlendirme protokolleri tarafından kullanılır.

Tanım

Algoritmanın girdisi, negatif olmayan ağırlıktaki yaylara sahip ağırlıklı yönlendirilmiş bir grafiktir. Çıktı, belirli bir tepe noktasından diğerlerine giden en kısa yolların bir kümesidir.

Başlangıçta, ilk tepe noktasının mesafesinin sıfır olduğu varsayılır ve diğerlerine olan mesafelerin sonsuz olduğu kabul edilir. Köşenin geçip geçmediğini gösteren bir dizi bayrak sıfırlarla doldurulur. Daha sonra, döngünün her adımında, ilk olana minimum mesafeli bir köşe ve sıfıra eşit bir bayrak aranır. Bunun için bir bayrak ayarlanır ve tüm komşu köşeler kontrol edilir. Kaynak tepe noktasından kontrol edilene olan önceden hesaplanmış mesafe, mevcut tepe noktasına olan mesafenin ve ondan kontrol edilen tepe noktasına olan kenarın uzunluğunun toplamından büyükse, kontrol edilen tepe noktasına olan mesafe şuna eşittir: mevcut olana olan mesafe + mevcut olandan kontrol edilene olan kenar. Döngü, tüm köşelerin bayrakları 1'e eşit olduğunda veya 0 bayraklı tüm köşelere olan mesafe sonsuz olduğunda sona erer. İkinci durum, ancak ve ancak grafiğin bağlantısının kesilmesi durumunda mümkündür.

Dijkstra'nın algoritması sözde kodda

Giriş: İTİBAREN: gerçek dizisi – grafik yaylarının uzunluk matrisi; s, en kısa yolun arandığı tepe noktasıdır ve t, arandığı tepe noktasıdır.

Çıktı: vektörler T: gerçek dizisi; ve H: 0..r dizisi. eğer üst v en kısa yolda yatıyor s ile t, sonra Televizyon]- en kısa yol uzunluğu s ile y; Peki] - hemen önceki zirve de en kısa yolda.

H, n köşesinin m köşesine karşılık geldiği, öncekinin s'den n'ye giden yolda olduğu bir dizidir.

T, köşe n'nin ondan s'ye olan mesafeye karşılık geldiği bir dizidir.

X, n köşesinin, yolu biliniyorsa 1'e, değilse 0'a karşılık geldiği bir dizidir.

dizi başlatma:

için v 1'den R yapmak

T[v]: = ∞ (kısayol bilinmiyor)

X[v]: = 0 (tüm köşeler işaretlenmemiş)

H[s]: = 0 ( s önce hiçbir şey gelmez)

T[ler]:= 0 ( en kısa yolun uzunluğu 0...)

X[ler]:= 1 ( ...ve o biliniyor) v : = s (şimdiki üst)

M: (not güncellemesi)

için ve ∈ G( ve) yapmak

eğer X[i] = 0 & T[u]> Televizyon] + C sonra

T[u]: = Televizyon] + C(daha kısa bir yol buldu s içinde ve vasıtasıyla v }

h[u]:= v(Bunu hatırlamak)

m: = ∞

v : = 0

(en kısa yolun sonunu bulmak)

için ve 1'den p yapmak

eğer X[u] = 0 &T[u]< t sonra

v:= sen;

m:= T[u]( tepe v gelen en kısa yolu bitirir s

eğer v = 0 o zaman

dur (çıkış yok s içinde t) eğer biter

eğer v= t sonra

dur ( en kısa yolu buldu s içinde t) eğer biter

X[v]: = 1 ( en kısa yolu buldu s içinde v ) git M

Gerekçe

Dijkstra'nın algoritmasının doğruluğunu kanıtlamak için, M etiketiyle başlayan döngü gövdesinin her yürütmesi için şunu belirtmek yeterlidir: v tepe noktasından en kısa yolun bilindiği bir tepe noktası kullanılır s. Diğer bir deyişle, X[v] = 1 ise T[v] = d(s,v) , ve H vektörü tarafından tanımlanan yol (s, v) üzerindeki tüm köşeler aynı özelliğe sahiptir, yani.

Vu T[u] = 1 => T[u] = d(s,u)&T] = 1.

Gerçekten de (tümevarım yoluyla), ilk kez v en kısa yolun boş olduğu ve uzunluğu 0 olan s köşesi kullanılır (yay uzunlukları negatif olmadığı için boş olmayan yollar daha kısa olamaz). T[u] = d(s,u) olsun önceden etiketlenmiş tüm köşeler için ve. Yeni etiketlenmiş köşeyi düşünün v, T[v] = min T[u] koşulundan seçilir. Etiketli köşelerden geçen yol biliniyorsa, en kısa yolun bilindiğine dikkat edin. (Aksine) varsayalım ki T[v] > d(s, v), yani bulunan yol s içinde v, en kısa değildir. O zaman bu yol üzerinde etiketlenmemiş köşeler olmalıdır. İlk köşeyi düşünün w bu yolda öyle ki T[w] = 0.Bizim var: T[w] = d(s,w)⩽d(s>v)< Т[v],что противоречит выбору вершины u.

Zaman karmaşıklığı

Dijkstra'nın algoritmasının karmaşıklığı, orijinal olana minimum mesafe ile ziyaret edilmemiş bir tepe noktasının nasıl bulunacağına, ziyaret edilmeyen tepe noktalarının nasıl saklanacağına ve etiketlerin nasıl güncelleneceğine bağlıdır. Grafikteki köşe sayısı n, kenar sayısı m olsun. Daha sonra, en basit durumda, orijinal tepe noktasına minimum mesafeye sahip tepe noktasını bulmak için tüm köşe kümesi arandığında ve mesafeleri depolamak için bir dizi kullanıldığında, algoritmanın çalışma süresi O(n 2)'dir. . Ana döngü yaklaşık n kez yürütülür, her birinde minimumu bulmak için yaklaşık n işlem harcanır. Ziyaret edilen her köşenin komşuları arasında dolaşmak, kenar sayısı m ile orantılı bir dizi işlem gerektirir (çünkü her kenar bu döngülerde tam olarak iki kez meydana gelir ve sabit sayıda işlem gerektirir). Böylece, algoritmanın toplam çalışma süresi O(n 2 +m) olur, ancak m, n(n-1)'den çok daha küçük olduğu için, O(n 2) olur.

Seyrek grafikler için (yani, m'nin n²'den çok daha az olduğu), ziyaret edilmeyen köşeler ikili bir yığında saklanabilir ve mesafe değerleri anahtar olarak kullanılabilir. Döngü yaklaşık n kez yürütüldüğünden ve gevşeme sayısı (etiket değişiklikleri) m'den fazla olmadığından, böyle bir uygulamanın çalışma süresi O(nlogn+mlogn)

Örnek

Geçilebilir köşeler tarafından köşe 1'den uzaklıkların hesaplanması:

En kısa yolu bulma örneğini düşünün. Şehrin bölgelerini birbirine bağlayan bir otoyol ağı verilmiştir. Bazı yollar tek yönlüdür. Şehir merkezinden bölgedeki her şehre giden en kısa yolları bulun.

Bu sorunu çözmek için kullanabilirsiniz Dijkstra'nın algoritması- 1959'da Hollandalı bilim adamı E. Dijkstra tarafından icat edilen grafikler üzerine bir algoritma. Grafiğin köşelerinden birinden diğerlerine olan en kısa mesafeyi bulur. Yalnızca negatif ağırlıklı kenarları olmayan grafikler için çalışır.

1. köşeden diğerlerine olan en kısa mesafeleri bulmak istensin.

Daireler köşeleri, çizgiler ise aralarındaki yolları (grafiğin kenarları) gösterir. Köşe sayıları dairelerde gösterilir, ağırlıkları kenarların üzerinde gösterilir - yolun uzunluğu. Her köşenin yanında kırmızı bir etiket işaretlenir - bu köşeye köşe 1'den en kısa yolun uzunluğu.

Köşe 1'in etiketinin kendisinin 0 olduğu varsayılır, kalan köşelerin etiketlerine ulaşılamaz Büyük sayı(ideal olarak - sonsuzluk). Bu, köşe 1'den diğer köşelere olan mesafelerin henüz bilinmediğini yansıtır. Grafiğin tüm köşeleri ziyaret edilmemiş olarak işaretlenir.

İlk adım

Vertex 1 minimum etikete sahiptir.Vertices 2, 3 ve 6 onun komşularıdır.Vertex'in komşularını sırayla atlarız.

Köşe 1'in ilk komşusu köşe 2'dir çünkü ona giden yolun uzunluğu minimumdur. Köşe 1'den ona giden yolun uzunluğu, köşe 1'e olan en kısa mesafenin, etiketinin değerinin ve 1'den 2'ye giden kenarın uzunluğunun toplamına eşittir, yani 0 + 7 = 7. Bu, mevcut köşe 2 (10000) etiketinden daha azdır, bu nedenle 2. köşenin yeni etiketi 7'dir.


Benzer şekilde, diğer tüm komşular için yol uzunluklarını buluruz (3 ve 6 nolu tepe noktaları).

Düğüm 1'in tüm komşuları kontrol edilir. Zirve 1'e mevcut minimum mesafe nihai olarak kabul edilir ve revizyona tabi değildir. Vertex 1 ziyaret edildi olarak işaretlendi.

İkinci adım

Algoritmanın 1. adımı tekrarlanır. Yine, ziyaret edilmeyen köşelerin “en yakınını” buluyoruz. Bu, 7 etiketli köşe 2'dir.

Yine, seçilen köşenin komşularının etiketlerini küçültmeye, 2. köşeden geçmeye çalışıyoruz. Köşe 2'nin komşuları 1, 3 ve 4 köşeleridir.

Vertex 1 zaten ziyaret edildi. Köşe 2'nin bir sonraki komşusu, ziyaret edilmemiş olarak işaretlenmiş köşelerin minimum etiketine sahip olduğundan, köşe 3'tür. 2 üzerinden giderseniz, böyle bir yolun uzunluğu 17'ye (7 + 10 = 17) eşit olacaktır. Ancak üçüncü köşenin mevcut etiketi 9 ve 9'dur.< 17, поэтому метка не меняется.


Köşe 2'nin bir diğer komşusu köşe 4'tür. 2. köşeden ona gidersek, böyle bir yolun uzunluğu 22'ye eşit olacaktır (7 + 15 = 22). 22'den beri<10000, устанавливаем метку вершины 4 равной 22.

Köşe 2'nin tüm komşuları görüntülendi, bu yüzden onu ziyaret edildi olarak işaretliyoruz.

Üçüncü adım

Algoritmanın adımını tepe 3'ü seçerek tekrarlıyoruz. “İşlenmesinden” sonra aşağıdaki sonuçları alıyoruz.

Dördüncü adım

Beşinci adım

altıncı adım

Böylece, köşe 1'den köşe 5'e en kısa yol, köşelerden geçen yol olacaktır. 1 — 3 — 6 — 5 , çünkü bu şekilde minimum 20 ağırlık kazanırız.

En kısa yola bir göz atalım. Her köşe için yolun uzunluğunu biliyoruz ve şimdi köşeleri sondan ele alacağız. Son tepe noktasını düşünün (bu durumda tepe noktası 5 ) ve bağlı olduğu tüm köşeler için, ilgili kenarın ağırlığını son tepe noktasının yol uzunluğundan çıkararak yol uzunluğunu buluruz.
Evet, üst 5 yol uzunluğu var 20 . O zirveye bağlı 6 ve 4 .
üst için 6 ağırlığını al 20 - 9 = 11 (eşleşti).
üst için 4 ağırlığını al 20 - 6 = 14 (eşleşmedi).
Sonuç olarak, söz konusu tepe noktasının yol uzunluğuyla eşleşen bir değer alırsak (bu durumda, tepe noktası 6 ), o zaman ondan son tepe noktasına geçiş yapıldı. Bu köşeyi istenen yolda işaretliyoruz.
Ardından, tepe noktasına ulaştığımız kenarı belirliyoruz. 6 . Ve böylece başlangıca ulaşana kadar.
Böyle bir geçiş sonucunda, bir adımda birkaç köşe için aynı değerlere sahipsek, bunlardan herhangi birini alabiliriz - birkaç yol aynı uzunluğa sahip olacaktır.

Dijkstra Algoritmasının Uygulanması

Grafik ağırlıklarını saklamak için bir kare matris kullanılır. Grafiğin köşeleri satır ve sütunların başlıklarındadır. Ve grafik yaylarının ağırlıkları tablonun iç hücrelerine yerleştirilir. Grafik döngüler içermez, bu nedenle matrisin ana köşegeni sıfır değerleri içerir.

	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++'da Uygulama

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_UYARILAR
#Dahil etmek
#Dahil etmek
#define BOYUT 6
int ana()
{
int a; // bağlantı matrisi
int d; // minimum mesafe
televizyonda; // ziyaret edilen köşeler
int temp, miniindex, min;
int başlangıç_dizini = 0;
sistem("chcp 1251");
sistem("cls");
// İlişki matrisinin başlatılması
for (int ben = 0; ben {
a[i][i] = 0;
for (int j = ben + 1; j yazdırf( "%d - %d mesafesini girin: ", ben+1, j+1);
scanf("%d" , &temp);
a[i][j] = sıcaklık;
a[j][i] = sıcaklık;
}
}
// İlişki matrisini göster
for (int ben = 0; ben {
for (int j = 0; j printf("%5d " , a[i][j]);
printf("\n");
}
// Köşeleri ve mesafeleri başlat
for (int ben = 0; ben {
d[i] = 10000;
v[i] = 1;
}
d=0;
// Algoritma adımı
yapmak(
mini dizin = 10000;
min = 10000;
for (int ben = 0; ben { // Köşe henüz ziyaret edilmemişse ve ağırlık min.
if ((v[i] == 1) && (d[i] { // değerleri yeniden ata
min = d[i];
miniindex=i;
}
}
// Bulunan minimum ağırlığı ekle
// geçerli köşe ağırlığına
// ve mevcut minimum köşe ağırlığı ile karşılaştırın
if (minindex != 10000)
{
for (int ben = 0; ben {
eğer (a[i] > 0)
{
sıcaklık = min + a[i];
eğer (sıcaklık< d[i])
{
d[i] = sıcaklık;
}
}
}
v = 0;
}
) while (mini dizin< 10000);
// Köşelere en kısa mesafeleri göster
yazdırf( "\nKöşelere en kısa mesafe: \n");
for (int ben = 0; ben printf("%5d ", d[i]);

// Yolu Geri Yükle
evirici; // ziyaret edilen köşeler dizisi
int bitiş = 4; // bitiş köşe indeksi = 5 - 1
ver = bitiş + 1; // başlangıç ​​elemanı - bitiş noktası
int k = 1; // önceki zirvenin indeksi
int ağırlık = d; // köşe ağırlığını sonlandır

while (bitiş !=başlangıç_dizini) // başlangıç ​​köşesine ulaşana kadar
{
for (int ben = 0; ben // tüm köşelere bak
eğer (a[i] != 0) // bir bağlantı varsa
{
int sıcaklık = ağırlık - a[i]; // önceki tepe noktasından yolun ağırlığını belirle
if (temp == d[i]) // ağırlık hesaplananla eşleşirse
{ // bu köşeden bir geçiş olduğu anlamına gelir
ağırlık = sıcaklık; // yeni ağırlığı kaydet
bitiş = ben; // önceki köşeyi kaydet
ver[k] = ben + 1; // ve bir diziye yaz
k++;
}
}
}
// Yolun görüntülenmesi (başlangıç ​​köşesi k elemanlı dizinin sonundadır)
yazdırf( "\nEn kısa yolu çıkar\n");
for (int i = k - 1; ben >= 0; i--)
printf("%3d ", ver[i]);
getchar(); getchar();
0 döndür;
}

Yürütme sonucu


Geri:

Köşeleri ve kenarları olan yönlendirilmiş veya yönlendirilmemiş ağırlıklı bir grafik verildi. Tüm kenarların ağırlıkları negatif değildir. Bazı başlangıç ​​köşeleri belirtildi. Bir tepe noktasından diğer tüm tepe noktalarına kadar olan en kısa yolların uzunluklarını bulmak ve ayrıca en kısa yolların kendilerinin çıktısını almak için bir yol sağlamak gerekir.

Bu soruna tek kaynaklı en kısa yol sorunu denir.

algoritma

Bu, Hollandalı araştırmacı tarafından önerilen algoritmayı açıklar. Dijkstra(Dijkstra) 1959'da

Her köşe için en kısa yolun mevcut uzunluğunu depolayacağımız bir dizi alalım. Başlangıçta ve diğer tüm köşeler için, bu uzunluk sonsuza eşittir (bir bilgisayarda uygulandığında, genellikle, olası yol uzunluğundan açıkça daha büyük olan, sonsuzluk olarak yeterince büyük bir sayı seçilir):

Ek olarak, her köşe için hala etiketli olup olmadığını saklayacağız, yani. bir boolean dizisi alalım. Başlangıçta, tüm köşeler etiketsizdir, yani.

Dijkstra'nın algoritmasının kendisi şunlardan oluşur: yinelemeler. Bir sonraki yinelemede, henüz etiketlenmemiş olanlar arasında en küçük değere sahip köşe seçilir, yani:

(İlk yinelemede başlangıç ​​tepe noktasının seçileceği açıktır.)

Bu şekilde seçilen tepe noktası işaretlenir. Ayrıca, mevcut yinelemede, tepe noktasından, gevşeme: tepe noktasından çıkan tüm kenarlara bakılır ve bu tür her bir tepe noktası için algoritma değerini iyileştirmeye çalışır. Geçerli kenarın uzunluğu olsun, sonra bir kod biçiminde gevşeme şöyle görünür:

Bu, mevcut yinelemenin bittiği yerdir, algoritma bir sonraki yinelemeye geçer (yine, en küçük değere sahip köşe seçilir, ondan gevşemeler yapılır, vb.). Bu durumda, sonunda, iterasyonlardan sonra grafiğin tüm köşeleri etiketlenecek ve algoritma işini tamamlayacaktır. Bulunan değerlerin, ile arasındaki en kısa yolların gerekli uzunlukları olduğu iddia edilmektedir.

Grafiğin tüm köşelerine köşe noktasından ulaşılamıyorsa, o zaman onlar için değerlerin sonsuz kalacağını belirtmekte fayda var. Algoritmanın son birkaç yinelemesinin sadece bu köşeleri seçeceği açıktır, ancak bu yinelemeler herhangi bir yararlı iş üretmeyecektir (çünkü sonsuz bir mesafe diğer, hatta sonsuz mesafeleri gevşetemez). Bu nedenle, seçilen tepe noktası olarak sonsuz mesafeli bir tepe noktası alınır alınmaz algoritma hemen durdurulabilir.

Yol geri yükleme. Tabii ki, genellikle sadece en kısa yolların uzunluklarını değil, aynı zamanda yolların kendilerini de bilmek gerekir. Herhangi bir tepe noktasından en kısa yolun daha sonra yeniden yapılandırılması için yeterli bilginin nasıl saklanacağını gösterelim. Bunun için sözde ata dizisi: her tepe noktası için, tepe noktasına giden en kısa yolda sondan bir önceki tepe noktasının numarasını tutan bir dizi. Bu, bir köşe noktasına giden en kısa yolu alır ve ardından bu yoldan son köşeyi kaldırırsak, bir köşe ile biten bir yol elde ettiğimizi ve bu yolun köşe için en kısa olacağı gerçeğini kullanır. Yani, eğer bu atalar dizisine sahipsek, o zaman en kısa yol ondan geri yüklenebilir, basitçe her seferinde atayı mevcut tepe noktasından alarak başlangıç ​​tepe noktasına ulaşana kadar - bu şekilde istenen en kısa yolu elde ederiz, ancak şu şekilde yazılır: Ters sipariş. Yani zirveye giden en kısa yol:

Bu atalar dizisinin nasıl inşa edileceğini anlamak için kalır. Ancak, bu çok basit bir şekilde yapılır: her başarılı gevşeme ile, yani. seçilen tepe noktasından bazı tepe noktalarına olan mesafede bir gelişme olduğunda, tepe noktasının atasının tepe olduğunu yazıyoruz:

Kanıt

Ana Açıklama Dijkstra'nın algoritmasının doğruluğunun dayandığı , aşağıdaki gibidir. Herhangi bir tepe noktası işaretlendikten sonra, ona olan mevcut mesafenin zaten en kısa olduğu ve buna göre artık değişmeyeceği belirtilmektedir.

Kanıt indüksiyonla üreteceğiz. İlk yineleme için geçerliliği açıktır - en kısa yolun uzunluğu olan sahip olduğumuz köşe için. Şimdi bu iddianın önceki tüm yinelemeler için geçerli olmasına izin verin, yani. tüm zaten işaretlenmiş köşeler; mevcut yinelemenin yürütülmesinden sonra ihlal edilmediğini kanıtlayalım. Geçerli yinelemede seçilen tepe noktası olsun, yani. algoritmanın etiketleyeceği tepe noktası. Bunun gerçekten ona giden en kısa yolun uzunluğuna eşit olduğunu ispatlayalım (bu uzunluğu ile gösteriyoruz).

Zirveye giden en kısa yolu düşünün. Açıkça, bu yol iki yola ayrılabilir: yalnızca işaretli köşelerden (en azından başlangıç ​​köşesi bu yolda olacaktır) ve yolun geri kalanından (işaretli köşeleri de içerebilir, ancak her zaman bir ile başlar) oluşur. işaretsiz). Yolun ilk tepe noktası ve yolun son tepe noktası ile belirtin.

Önce tepe noktası için iddiamızı ispatlayalım, yani, eşitliğini ispatlayalım. Bununla birlikte, bu neredeyse açıktır: sonuçta, önceki yinelemelerden birinde bir tepe noktası seçtik ve ondan gevşeme gerçekleştirdik. (Tam tepe noktası seçimi sayesinde) en kısa yol artı kenar için en kısa yola eşit olduğundan, o zaman gevşeme gerçekleştirildiğinde, değer gerçekten gerekli değere ayarlanacaktır.

Kenarların maliyetlerinin negatif olmamasından dolayı, en kısa yolun uzunluğu (bu, az önce kanıtlanana göre 'ye eşittir), tepe noktasına giden en kısa yolun uzunluğunu aşmaz. Sonuç olarak (sonuçta Dijkstra'nın algoritması genellikle mümkün olandan daha kısa bir yol bulamadı) göz önüne alındığında, aşağıdaki bağıntıları elde ederiz:

Öte yandan, hem ve ve hem de etiketlenmemiş köşeler olduğundan, geçerli yinelemede seçilen köşe olduğu ve köşe noktası olmadığı için, başka bir eşitsizlik elde ederiz:

Bu iki eşitsizlikten eşitliği çıkarıyoruz ve daha sonra bulunan ilişkilerden elde ediyoruz ve:

Q.E.D.

uygulama

Böylece, Dijkstra'nın algoritması, her birinde en küçük değere sahip etiketlenmemiş bir tepe noktasının seçildiği, bu tepe noktasının etiketlendiği ve daha sonra bu tepe noktasından dışarı çıkan tüm kenarların gözden geçirildiği ve her kenar boyunca iyileştirme için bir girişimde bulunulan yinelemelerden oluşur. kenarın diğer ucundaki değer.

Algoritmanın çalışma süresi aşağıdakilerin toplamıdır:

Bu işlemlerin en basit uygulamasıyla, işlemler bir tepe noktası bulmaya, işlemler bir gevşemeye ve son işlemlere harcanacaktır. asimptotik algoritma:

uygulama:

const int INF = 1000000000 ; int main() ( int n; ... oku n ... vektör< vector < pair< int ,int >> > g(n); ... grafik okuma... int s = ...; // başlangıç ​​noktası vektör< int >d(n, INF), p(n) ; d[s] = 0; vektör< char >u(n); for (int i= 0 ; ben< 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; } } } }

Burada grafik, bitişik listeler biçiminde saklanır: her köşe için liste, bu köşeden çıkan kenarların bir listesini içerir, yani. çiftlerin bir listesi >, burada çiftin ilk elemanı, kenarın götürdüğü tepe noktasıdır ve ikinci eleman, kenarın ağırlığıdır.

5.4.3. En kısa yol problemi ve bunu çözmek için Dijkstra'nın algoritması

Bir digraf verilmesine izin ver G(V, E), her yayına bir numara atanan
aranan yay uzunluğu.

Tanım. Uzunluk path, bu yolu oluşturan yayların uzunluklarının toplamıdır. En Kısa Yol Problemi böyle koyun.

Seçenek 1. Sabit bir tepe noktasından en kısa yolların (minimum uzunluktaki yollar) uzunluklarını ve yolların kendilerini bulun s grafiğin diğer tüm köşelerine.

Seçenek 2. Verilen grafikteki tüm köşe çiftleri arasındaki en kısa yolların uzunluklarını ve yolların kendilerini bulun.

Grafiğin yayları negatif uzunluktaysa, problemin çözümleri olmayabilir (anlamını kaybeder). Bunun nedeni, grafiğin negatif uzunlukta bir kontur içerebilmesidir. Negatif uzunlukta konturların varlığı, yolun uzunluğunun şuna eşit yapılabileceği anlamına gelir.
. Ve negatif uzunlukta konturlar yoksa, o zaman en kısa yollar vardır ve herhangi bir kısa yol basit bir zincirdir.

En kısa yol varsa, alt yollarından herhangi birinin aynı zamanda karşılık gelen köşeler arasındaki en kısa yol olduğuna dikkat edin.

Dijkstra'nın en kısa yol problemini çözme algoritması.

Algoritma, pozitif uzunluktaki yaylarla çalışır ve sabit bir tepe noktasından en kısa yolları belirler. s grafiğin diğer tüm köşelerine. Bu köşeleri etiketleyelim v 1 , v 2 ,…, v n .

Tanım. tepe noktası diyelim sen tepeye daha yakın yalan süstten daha v gelen en kısa yolun uzunluğu ise sönceki sen gelen en kısa yolun uzunluğundan daha az sönceki v. zirveler diyeceğiz sen ve v eşit uzaklıktaÜstten s, en kısa yolların uzunlukları ise sönceki sen ve sönceki v kibrit.

Dijkstra'nın algoritması, bir köşe noktasına yakınlık açısından bir grafiğin köşelerini sırayla sıralar s ve aşağıdaki temel ilkelere dayanmaktadır.

Yay uzunlukları pozitif sayılar ise, o zaman

en yakın s üst kendisidir. gelen en kısa yolun uzunluğu sönceki s 0;

en yakın s köşe noktası dışında s, yalan s bir yay mesafesinde - tepe noktasından çıkan tüm yayların en kısası s;

gelen en kısa yolun herhangi bir ara tepe noktası s biraz zirveye kadar v daha yakın yatıyor s bitiş noktasından daha v;

sonraki sıralı köşeye giden en kısa yol, yalnızca önceden sıralanmış köşelerden geçebilir.

Algoritmanın köşeleri zaten sipariş etmesine izin verin v 1 , v 2 … v k . ile belirtmek
,
zirveye giden en kısa yolun uzunluğu v i .

Kümenin köşelerinden birinde başlayan orijinal grafiğin tüm yaylarını göz önünde bulundurun.
ve henüz sıralanmamış köşelerde sonlandırın. Bu tür her bir yay için, örneğin
, toplamı hesapla
. Bu toplam, gelen yolun uzunluğuna eşittir. s içinde y, hangisinde üst v i sondan bir önceki tepe noktası ve s içinde v i bağlanan tüm yolların en kısasıdır s ve v i .

Bu, tüm yolların uzunluklarını belirler. s sadece ara köşeler arasından köşelerin olduğu henüz sıralanmamış köşelere k en yakın s. Bu yolların en kısası en tepede bitsin w. O zamanlar w ve ye
yakın s köşe.

Teknik olarak, Dijkstra'nın algoritmasına göre eylemler, köşe etiketleri aparatı kullanılarak gerçekleştirilir. Köşe Etiketi v olarak belirtilir
. Her etiket, bazı yolların uzunluğuna eşit bir sayıdır. s önceki v. Etiketler geçici ve kalıcı olarak ikiye ayrılır. Her adımda yalnızca bir etiket kalıcı hale gelir. Bu, değerinin ilgili tepe noktasına giden en kısa yolun uzunluğuna eşit olduğu ve bu tepe noktasının kendisinin sıralandığı anlamına gelir. Bir sonraki sıralı köşenin numarası harfle gösterilir. R.

Algoritmanın açıklaması.

Aşama 1. (İlk ayar). Koy
ve bu etiketi kalıcı olarak kabul edin. Koy
,
ve bu etiketleri geçici olarak ele alın. Koy
.

Adım 2 (genel adım). tekrar eder n grafiğin tüm köşeleri sıralanana kadar

Zaman Damgasını Yeniden Hesapla
herhangi bir sırasız köşe v i, tepe noktasından ayrılan yayı içeren R, kurala göre

Minimum zaman damgasına sahip tepe noktasını seçin. Bu tür birkaç köşe varsa, herhangi birini seçin.

İzin vermek w- minimum zaman damgalı tepe noktası. Etiketi oku
sabit ve koymak
.

Dijkstra algoritmasının adımlarını, her sütunu grafiğin bir köşesine karşılık gelen bir tabloda düzenlemek uygundur. Tablonun satırları, ortak adımın tekrarına karşılık gelir.

Örnek. Şekildeki grafik için 4. Köşelerden en kısa yolları bulun
grafiğin diğer tüm köşelerine. Kenarlar, aynı uzunlukta iki farklı yönlendirilmiş yay anlamına gelir.

Çözüm. Masada. Her adımda 1 adet köşe etiketi yazılır. Kalıcı işaretler "+" işaretiyle işaretlenmiştir. Köşe etiketlerinin nasıl hesaplandığını detaylı olarak anlatalım.

Köşe 1'den yaylar 2, 5, 6 köşelerine gider. Bu köşelerin etiketlerini yeniden hesaplayın ve tablonun ikinci satırını doldurun.

Vertex etiketi 6 kalıcı hale gelir,
.

6. köşeden, yaylar hala sıralanmamış 2, 5, 8, 9 köşelerine gider. Zaman damgalarını yeniden hesaplayın

Tablonun 3. satırını doldurun. Zaman damgalarının minimumu 3'tür (köşe etiketi 9),
.

Köşe 9'dan, yaylar hala sıralanmamış köşeler 5, 8, 11, 12'ye gider.

Tablonun dördüncü satırını doldurun. Bu satırda iki köşe - 2 ve 12'nin minimum zaman damgası 4'e eşittir. İlk olarak, örneğin köşe 2'yi sıralayalım. Ardından, bir sonraki adımda köşe 12 sıralanacak.

tablo 1

Yani,
.

2. köşeden, yaylar hala sıralanmamış olan 3, 4, 5 köşelerine gider. Bu köşelerin zaman damgalarını yeniden hesaplayın.

Tablonun 5. satırını doldurun. Zaman damgalarının minimumu 4'tür (köşe etiketi 12),
.

Tablonun 6. satırını doldurun. Zaman damgalarının minimumu 5'tir (köşe etiketi 5),
.

Tablonun 7. satırını doldurun. Köşe etiketi 8 sabit hale gelir (5'e eşittir),
.

Vertex 11 sipariş edildi.

Köşe 11'den yaylar sırasız 7, 10 köşelerine gider. Bu köşelerin zaman damgalarını yeniden hesaplayın

Vertex 4 kalıcı bir etiket alır.

Köşe 4'ten, yaylar sırasız köşe 3, 7'ye gider. Zaman damgalarını yeniden hesaplayın

İlk 3'ü düzenleyin.

Tablonun 12. satırını doldurun. Bu adımda, son sırasız köşe 10'u sipariş ediyoruz.

En kısa yollardan oluşan bir ağaç inşa etmek.

En kısa yol ağacı, bir tepe noktasında köklenmiş yönlendirilmiş bir ağaçtır. S . Bu ağaçtaki tüm yollar, bu grafik için en kısa yollardır.

En kısa yol ağacı tabloya göre oluşturulur, tepe noktası tepe noktası kalıcı etiketleri aldıkları sıraya dahil edilir. Kök, ağaca dahil edilecek ilk düğümdür. S .

Örneğimiz için en kısa yollardan oluşan bir ağaç oluşturalım.

İlk olarak, ağaca 1 nolu kökü ekliyoruz, ardından yay (1,6) ağaca dahil ediliyor. Daha sonra, en kısa yolun uzunluğu 3'e eşit olan Vertex 9 sipariş edildi.
. Bu nedenle, köşe 6, köşe 9'a giden en kısa yolun sondan bir önceki köşesidir. Ağaca 1 uzunluğundaki yayı (6,9) dahil ediyoruz.

Daha sonra köşe 2, en kısa yol uzunluğu 4'e eşit olacak şekilde sipariş edildi.
. Sonuç olarak, ikinci tepe noktasına giden en kısa yol yay (6,2) boyunca geçer. 2 uzunluğundaki yayı (6,2) ağaca dahil ediyoruz.

Ardından, köşe 12 sipariş edildi,
. 4 sayısı ilk kez, doldurulduğunda doldurulan dördüncü satırda görünür.
. 1 uzunluğundaki yay (9,12) ağaca dahil edilmiştir.En kısa yolların tam ağacı şek. 5.

Grafiğin negatif uzunlukta yayları varsa Dijkstra'nın algoritması başarısız olabilir. Yani, en kısa yolları yukarıdan aramak s =1 şek. 6, algoritma önce düğüm 3'ü, ardından düğüm 2'yi sipariş edecek ve bitirecektir. Ayrıca, Dijkstra'nın algoritması açısından tepe 3'e giden bu en kısa yol, uzunluk 3 olan bir yaydır (1,3).

Aslında, köşe 3'e giden en kısa yol (1,2) ve (2,3) yaylarından oluşur, bu yolun uzunluğu 5+(-3)=2'dir.

Negatif uzunluk -3 olan bir yayın (2,3) varlığı nedeniyle, aşağıdaki temel ilkeler ihlal edildi:

en yakın s köşe, ondan iki yay uzaklıkta yer alır, bir değil;

en kısa yolun 1-2-3 (köşe 2) ara tepe noktası, yol 3'ün son tepe noktasından 1 tepe noktasından (mesafe 5) daha uzaktadır.

Bu nedenle, negatif uzunluktaki yayların varlığı, en kısa yol probleminin çözümünü zorlaştırır ve Dijkstra'nın algoritmasından daha karmaşık algoritmaların kullanılmasını gerektirir.

Bir grafikteki en kısa yolları bulmaya yönelik birçok algoritmadan Habre'de yalnızca Floyd-Warshall algoritmasının bir tanımını buldum. Bu algoritma, grafiğin tüm köşeleri ve uzunlukları arasındaki en kısa yolları bulur. Bu yazıda, belirli bir köşe (kaynak) ile grafiğin diğer tüm köşeleri arasındaki optimal yolları ve uzunluklarını bulan Dijkstra algoritmasının çalışma prensibini anlatacağım. Bu algoritmanın dezavantajı, grafiğin negatif ağırlıklı yaylara sahip olması durumunda düzgün çalışmamasıdır.

Örneğin, aşağıdaki yönlendirilmiş grafiği G alın:

Bu grafiği bir C matrisi olarak gösterebiliriz:

1 nolu köşeyi kaynak olarak alalım.Bu, 1 nolu tepe noktasından 2, 3, 4 ve 5 nolu tepe noktalarına kadar olan en kısa yolları arayacağız demektir.
Bu algoritma adım adım grafiğin tüm köşeleri boyunca yinelenir ve bunlara kaynak tepe noktasından belirli bir tepe noktasına bilinen minimum mesafe olan etiketler atar. Bu algoritmayı bir örnekle ele alalım.

1. köşeye 0'a eşit bir etiket atayalım, çünkü bu köşe kaynaktır. Kalan köşelere sonsuza eşit etiketler atanacaktır.

Daha sonra, minimum etikete sahip bir W köşesi seçiyoruz (şimdi köşe 1'dir) ve W köşesinden arabulucu köşeler içermeyen bir yolun olduğu tüm köşeleri göz önünde bulunduruyoruz. Değerlendirilen köşelerin her birine, W etiketinin toplamına ve W'den incelenen köşeye giden yolların uzunluğuna eşit bir etiket atarız, ancak yalnızca elde edilen toplam etiketin önceki değerinden küçükse. Miktar daha az değilse, önceki etiketi değiştirmeden bırakırız.

W'den doğrudan bir yol olan tüm köşeleri düşündükten sonra, W köşesini ziyaret edildi olarak işaretliyoruz ve henüz ziyaret edilmemişlerden minimum etiket değerine sahip olanı seçiyoruz, bir sonraki köşe W olacak. bu durumda, bu köşe 2 veya 5'tir. Aynı etiketlere sahip birkaç köşe varsa, hangisini W olarak seçtiğimizin önemi yoktur.

2. köşeyi seçiyoruz. Ama ondan giden bir yol yok, bu yüzden hemen bu köşeyi ziyaret edildi olarak işaretliyoruz ve minimum etiketle bir sonraki köşeye geçiyoruz. Bu sefer sadece köşe 5 minimum etikete sahiptir. 5'ten doğrudan yolların olduğu, ancak henüz ziyaret edilmiş olarak işaretlenmemiş tüm köşeleri göz önünde bulundurun. Yine W köşesinin etiketinin toplamını ve W'den mevcut köşeye kadar olan kenarın ağırlığını buluyoruz ve bu toplam önceki etiketten küçükse, o zaman etiketin değerini ortaya çıkan toplamla değiştiriyoruz.

Resme dayanarak 3. ve 4. köşelerin etiketlerinin küçüldüğünü, yani kaynak köşeden bu köşelere daha kısa bir rota bulunduğunu görebiliriz. Ardından, 5. tepe noktasını ziyaret edildi olarak işaretleyin ve minimum etikete sahip bir sonraki tepe noktasını seçin. Görülmemiş köşeler olduğu sürece yukarıdaki tüm eylemleri tekrarlıyoruz.

Tüm adımları tamamladıktan sonra aşağıdaki sonucu alıyoruz:

Ayrıca, en kısa rotaları oluşturabileceğiniz bir P vektörü de vardır. Eleman sayısı ile bu vektör, grafikteki köşe sayısına eşittir.Her eleman, kaynak tepe noktası ile son tepe noktası arasındaki en kısa yol üzerindeki son ara tepe noktasını içerir. Algoritmanın başlangıcında, P vektörünün tüm elemanları kaynak tepe noktasına eşittir (bizim durumumuzda, P = (1, 1, 1, 1, 1)). Ayrıca, dikkate alınan tepe noktası için etiket değerinin yeniden hesaplanması aşamasında, dikkate alınan tepe noktasının etiketi daha küçük bir değere dönüşürse, mevcut tepe noktasının değerini P dizisine yazarız. Örneğin: 3. tepe noktasının bir değeri vardır. W=1 ile "30" değerine sahip etiket. Ayrıca, W=5'te 3. köşenin etiketi "20" olarak değişti, bu nedenle değeri P - P=5 vektörüne yazacağız. Ayrıca, W=5'te, 4. köşedeki etiketin değeri değişmiştir ("50" idi, "40" oldu), bu, P vektörünün 4. elemanına W - P değerinin atanması gerektiği anlamına gelir. =5. Sonuç olarak, Р = (1, 1, 5, 5, 1) vektörünü elde ederiz.

P vektörünün her bir elemanının, kaynak ile son tepe noktası arasındaki yol üzerindeki son ara tepe noktasını içerdiğini bilerek, en kısa rotanın kendisini elde edebiliriz.