DAA - En Kısa Yollar

Dijkstra Algoritması

Dijkstra'nın algoritması, tek kaynaklı en kısa yollar problemini yönlendirilmiş ağırlıklı bir grafik G = (V, E) üzerinde çözer , burada tüm kenarlar negatif değildir (yani, her kenar için w (u, v) ≥ 0 (u, v ) Є E ).

Aşağıdaki algoritmada bir işlev kullanacağız Extract-Min(), düğümü en küçük anahtarla çıkarır.

Algorithm: Dijkstra’s-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
S := Ф 
Q := G.V 
while Q ≠ Ф 
   u := Extract-Min (Q) 
   S := S U {u} 
   for each vertex v Є G.adj[u] 
      if v.d > u.d + w(u, v) 
         v.d := u.d + w(u, v) 
         v.∏ := u

Analiz

Bu algoritmanın karmaşıklığı tamamen Min Ayıkla işlevinin uygulanmasına bağlıdır. Çıkarım min fonksiyonu doğrusal arama kullanılarak uygulanırsa, bu algoritmanın karmaşıklığı şu şekildedir:O(V² + E).

Bu algoritmada, min-heap kullanırsak Extract-Min() işlev düğümü döndürmek için çalışır Q en küçük anahtar ile bu algoritmanın karmaşıklığı daha da azaltılabilir.

Misal

Tepe noktasını düşünelim 1 ve 9sırasıyla başlangıç ​​ve hedef köşe noktası olarak. Başlangıçta, başlangıç ​​köşesi dışındaki tüm köşeler ∞ ile işaretlenir ve başlangıç ​​köşesi ile işaretlenir0.

Köşe	İlk	Adım 1 V 1	Adım2 V 3	Adım3 V 2	Adım4 V 4	Adım5 V 5	Adım6 V 7	Adım7 V 8	Adım8 V 6
1	0	0	0	0	0	0	0	0	0
2	∞	5	4	4	4	4	4	4	4
3	∞	2	2	2	2	2	2	2	2
4	∞	∞	∞	7	7	7	7	7	7
5	∞	∞	∞	11	9	9	9	9	9
6	∞	∞	∞	∞	∞	17	17	16	16
7	∞	∞	11	11	11	11	11	11	11
8	∞	∞	∞	∞	∞	16	13	13	13
9	∞	∞	∞	∞	∞	∞	∞	∞	20

Bu nedenle, minimum tepe mesafesi 9 tepe noktasından 1 dır-dir 20. Ve yol

1 → 3 → 7 → 8 → 6 → 9

Bu yol, önceki bilgilere göre belirlenir.

Bellman Ford Algoritması

Bu algoritma, yönlendirilmiş bir grafiğin tek kaynaklı en kısa yol problemini çözer G = (V, E)kenar ağırlıklarının negatif olabileceği. Ayrıca, negatif ağırlıklı döngü yoksa bu algoritma en kısa yolu bulmak için uygulanabilir.

Algorithm: Bellman-Ford-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
for i = 1 to |G.V| - 1 
   for each edge (u, v) Є G.E 
      if v.d > u.d + w(u, v) 
         v.d := u.d +w(u, v) 
         v.∏ := u 
for each edge (u, v) Є G.E 
   if v.d > u.d + w(u, v) 
      return FALSE 
return TRUE

Analiz

İlk for döngü, başlatma için kullanılır. O(V)zamanlar. Sonrakifor döngü çalışmaları |V - 1| alan kenarlardan geçerO(E) zamanlar.

Dolayısıyla, Bellman-Ford algoritması O(V, E) zaman.

Misal

Aşağıdaki örnek Bellman-Ford algoritmasının adım adım nasıl çalıştığını göstermektedir. Bu grafiğin negatif bir kenarı vardır, ancak herhangi bir negatif döngüsü yoktur, bu nedenle problem bu teknik kullanılarak çözülebilir.

Başlatma sırasında, kaynak dışındaki tüm köşeler ∞ ile işaretlenir ve kaynak 0.

İlk adımda kaynaktan ulaşılabilen tüm köşeler minimum maliyetle güncellenir. Dolayısıyla, köşelera ve h güncellenir.

Bir sonraki adımda, köşeler a, b, f ve e güncellenir.

Aynı mantığı takip ederek, bu adımda köşeler b, f, c ve g güncellenir.

Burada, köşeler c ve d güncellenir.

Bu nedenle, tepe noktası arasındaki minimum mesafe s ve tepe d dır-dir 20.

Önceki bilgilere göre, yol s → h → e → g → c → d şeklindedir