Dijkstra'nın algoritması uygulamasında tüm düğümlerle 1 dizi ve tüm düğümlerle 1 öncelik sırası var. Bir düğüm devreden çıkarıldığında, tüm bitişik düğümleri yeni mesafeyle ve nereden geldiğini günceller, böylece yolu yeniden izleyebilirim.Dijkstra'nın öncelik sırasına göre algoritması
öncelik kuyruğundaki düğüm yeni mesafe ile güncellenir ve ondan yeni bir mesafede geldiği dizide düğüm güncellenir. Bir düğüm dequeued edildiğinde dizideki son mesafesi güncellenir:
PathInfo current = pq.remove();
path[current.pos].distance = current.distance;
önceki düğüm ve mesafe ile öncelikli sırası hakkındaki bilgilerle diziyi hem güncellemek için kabul edilebilir mi?
Bu, daha iyi bir mesafe olan her durumda olur:
PathInfo key(i, newDistance);
path[i].distance = newDistance;
path[i].previous = current.pos;
pq.decreaseKey(key);
gereksiz biraz temelde aynı bilgi ile benim dizi ve öncelikli sırayı güncellemek gibi görünüyor.
Şu anda PQ bir veri yapısı olarak düzenli bir dizi kullanıyorum. Önceliğin güncellenmesi doğrusal zamanda yapılır ve dequeueing de doğrusal zamanda yapılır. Öncelikli kuyruğunda kullanmalı ve nasıl bir düğümleri öncelik değiştirmek gerekenler veri yapısı
? Ben kullanabilir C++
Dizideki mesafeleri güncellemeliyim. PQ'mdan gelen düğüm, bitişik düğümlere daha iyi bir mesafe verebilirse nasıl karşılaştırmalıyım? – Carlj901
İdeal olarak, PQ'nuzdan bakabilmeniz gerekir. Bu işlem kullanılamıyorsa (ve PQ uygulamanıza eklenemiyorsa), gereksiz bilgileri korumanız gerekecektir. [Bu cevabımı bir cevaba ekleyeceğim] – comingstorm
En çok tercih edilen, PQ'mda bir yığın tutabilseydim ve her düğüm adını (2B dizisindeki konum) mesafeli olarak eşleyen bir karma işlevine sahip olsaydım olurdu. Bunu nasıl uygulayacağımı bilmiyorum. – Carlj901