Çizgi Roman: Dijkstra Algoritmasının Veri Yapısı Optimizasyonunun En Kısa Yolu | Teknik Başlıklar
Yazar Xiaohui, bu makale yetki ile programcı Xiaohui'den (ID: chengxuyuanxiaohui) yeniden basılmıştır.
Xiao Hui, "Çizgi Roman:" En Kısa Yol "Grafik Sorunu" adlı makalede, tek kaynaklı en kısa yol algoritması Dijkstra'yı tanıttı. O dönemde çizgi romanlarda bir sorun bıraktık: Sadece mesafeyi değil, en kısa yolun ayrıntılı düğümlerini nasıl bulabilirim? Bu yazıda cevaplar vereceğiz.
A tepe noktasından G tepe noktasına en kısa mesafeyi bulmak için hala aşağıdaki ağırlıklı grafiği örnek olarak alıyoruz.
Ayrıntılı süreç aşağıdaki gibidir:
İlk adım, bir uzaklık tablosu ve bir ön köşe tablosu oluşturmaktır.
Uzaklık tablosunun Anahtarı, tepe noktasının adıdır, Değer, başlangıç noktası A'dan karşılık gelen tepe noktasına bilinen en kısa mesafedir ve varsayılan sonsuzdur; Ön köşe tablosunun Anahtarı, tepe noktasının adıdır ve Değer, başlangıç noktası A'dan karşılık gelen tepe noktasına kadar bilinen en kısa yoldur. Önceden sabitlenmiş nokta.
İkinci adım, başlangıç noktası A'nın bitişiğindeki B ve C köşelerini bulmak için A başlangıç noktasını çaprazlamaktır. A'dan B'ye uzaklık 5, A'dan C'ye uzaklık 2'dir. Bu bilgiyi mesafe tablosuna güncelleyin.
Aynı zamanda, B ve C köşelerinin ön köşelerinin her ikisi de A'dır ve bitişik listesindeki A köşesinin alt simgesi 0'dır, bu nedenle ön köşe tablosunun B ve C değerleri 0 olarak güncellenir:
Üçüncü adım, uzaklık tablosundan A'dan itibaren en kısa noktayı, yani köşe C'yi bulmaktır.
Dördüncü adım, C köşesini geçmek ve C köşesinin bitişik D ve F köşelerini bulmaktır (A geçilmiştir, dikkate alınmasına gerek yoktur). C'den D'ye olan mesafe 6'dır, dolayısıyla A'dan D'ye uzaklık 2 + 6 = 8; C'den F'ye uzaklık 8'dir, dolayısıyla A'dan F'ye uzaklık 2 + 8 = 10'dur. Bu bilgileri tabloya yenileyin.
Aynı zamanda, D ve F köşelerinin ön köşelerinin her ikisi de C'dir ve bitişik listesindeki C köşesinin alt simgesi 2'dir, bu nedenle ön köşe tablosunun D ve F değerleri 2'ye güncellenir:
Ardından 3. ve 4. adımlarda yapılan işlemleri tekrarlayın:
Adım 3'ün tekrarı olan Adım 5, uzaklık tablosundan A'dan en kısa mesafeye sahip noktayı bulun (C geçilmiştir, dikkate alınmasına gerek yoktur), yani tepe noktası B'dir.
4. adımın tekrarı olan 6. adım, köşe B'yi çaprazlayın, B köşesinin bitişik D ve E köşelerini bulun (A çaprazlanmıştır, dikkate alınmasına gerek yoktur). B'den D'ye olan mesafe 1'dir, yani A'dan D'ye olan mesafe 5 + 1 = 6'dır, Mesafe tablosunda 8'den az ; B'den E'ye olan mesafe 6, yani A'dan E'ye olan mesafe 5 + 6 = 11'dir. Bu bilgileri tabloya yenileyin.
Aynı zamanda, D ve E köşelerinin ön köşelerinin her ikisi de B'dir ve bitişik tablodaki köşe B'nin alt simgesi 1'dir, bu nedenle ön köşe tablosunun D ve E değerleri 1 olarak güncellenir:
Adım 7, uzaklık tablosundan A'dan itibaren en kısa noktayı bulun (B ve C'nin dikkate alınması gerekmez), bu da köşe D'dir.
Adım 8, tepe noktasını D çaprazlayın, tepe noktasının E ve F bitişik köşelerini bulun. D'den E'ye olan mesafe 1'dir, dolayısıyla A'dan E'ye olan mesafe 6 + 1 = 7'dir, Mesafe tablosunda 11'den az ; D'den F'ye olan mesafe 2'dir, yani A'dan F'ye olan mesafe 6 + 2 = 8'dir, Mesafe tablosunda 10'dan az . Bu bilgileri tabloya yenileyin.
Aynı zamanda, E ve F köşelerinin ön köşelerinin her ikisi de D'dir ve bitişik listesindeki D köşesinin alt simgesi 3'tür, bu nedenle ön köşe tablosunun E ve F değerleri 3 olarak güncellenir:
Adım 9, uzaklık tablosundan A'dan itibaren en kısa noktayı, yani tepe E'yi bulun.
Adım 10: E tepe noktasını çaprazlayın ve E tepe noktasına bitişik G tepe noktasını bulun. E ile G arasındaki mesafe 7'dir, dolayısıyla A ile G arasındaki mesafe 7 + 7 = 14'tür. Bu bilgileri tabloya yenileyin.
Aynı zamanda, G tepe noktasının ön tepe noktası E'dir ve bitişik listesindeki E tepe noktasının alt simgesi 4'tür, bu nedenle ön tepe tablosunun G değeri 4 olarak güncellenir:
Adım 11: Uzaklık tablosundan A'dan itibaren en kısa noktayı, yani tepe F'yi bulun.
Adım 12: F tepe noktasını çaprazlayın ve F tepe noktasına bitişik G tepe noktasını bulun. F'den G'ye olan mesafe 3'tür, dolayısıyla A'dan G'ye olan mesafe 8 + 3 = 11'dir, Mesafe tablosunda 14'ten az . Bu bilgileri tabloya ekleyin:
Bu şekilde, bitiş noktası dışındaki tüm köşeler geçilmiştir Uzaklık tablosu, başlangıç noktası A'dan tüm köşelere kadar olan en kısa mesafeyi kaydeder ve önceden sabitlenmiş nokta, başlangıç noktası A'dan tüm köşelere kadar en kısa yolun ön köşesini depolar.
Ön köşe tablosu grafiğin en kısa yoluna nasıl "çevrilir"? Geriye doğru geri gitmek için geri izleme yöntemini kullanabiliriz:
Adım 1. Grafiğin en kısa yolun bitiş noktası olan G bitiş noktasını bulun:
İkinci adım, önceden sabitlenmiş nokta tablosu aracılığıyla G köşesine karşılık gelen ön alt simge 5'i bulmak ve köşe dizisindeki alt simge 5'e karşılık gelen F köşesini bulmaktır; bu, köşe G'nin ön köşe noktasıdır:
Üçüncü adım, önceden sabitlenmiş nokta tablosu aracılığıyla F köşesine karşılık gelen ön alt simge 3'ü bulmak ve köşe dizisinde F köşesinin ön köşe noktası olan alt simge 3'e karşılık gelen D köşesini bulmaktır:
Dördüncü adım, ön-sabit nokta tablosu aracılığıyla D tepe noktasına karşılık gelen ön alt simge 1'i bulmak ve köşe dizisinde alt simge 1'e karşılık gelen B tepe noktasını bulmaktır; bu, köşe D'nin ön tepe noktasıdır:
Beşinci adım, ön sabit nokta tablosu aracılığıyla B tepe noktasına karşılık gelen 0 ön alt simge bulmak ve köşe B'nin ön tepe noktası olan köşe dizisinde 0 alt simge A'ya karşılık gelen A tepe noktasını bulmaktır:
Bu şekilde, ön köşe tablosunu (0,0,1,3,3,5) en kısa yola (A-B-D-F-G) dönüştürüyoruz.
Kodda, hem uzaklık tablosu hem de ön köşe tablosu bir dizide saklanır, bu daha uygun olur.
En kısa yolun çıktısını alırken, kod geri dönüş için özyinelemeli bir yol kullanır.
