Minimum öncelikli sıraya sahip Dijkstra algoritması

Question

Dijkstra algoritmasını öncelik sırasına göre uygulamaya çalışıyorum ama nasıl çalıştığını anlayamıyorum. İnternette birçok rehber okudum ama bu algoritmayı hiç anlayamıyorum.

Sorum sorum: her düğüm için öncelik nedir? Minimun değeriyle gelen kenarın ağırlığı olduğunu düşünüyorum, ama emin değilim. Bu doğru mu?

İkinci soru, sıranın kökünü ayıkladığımda, bu düğümün ziyaret edilen düğümlerden hiçbiriyle bitişik olmaması durumunda nasıl çalışır?

Answer 1

vertex'un vertex başlangıç ​​noktasından en kısa mesafeye sahip olduğu en yüksek önceliği priority queue kullanmalısınız. İlk olarak, tüm vertices sonsuz kısa mesafeyi ve PQ içinde grafikten (onun edges) tüm vertices arasında sokulmasıyla vertex başlangıç ​​en kısa mesafe olacak 0

Başlangıç ​​olacaktır. vertex'u PQ numaralı telefondan çıkarın ve edges kodlarını keşfedin. Bitişikteki tüm vertices ile en kısa mesafeleri karşılaştırın ve herhangi bir mesafe geçerli vertex üzerinde en kısa mesafeden daha azsa, PQ içinde en kısa mesafeyi bitişik vertex güncelleştirin. Devam PQ boş değil. edges numarasına sahip olmayan Vertices, vertex başından itibaren 'onlara ulaşma' mümkün olmadığından en kısa sonsuzluk mesafesini bitirecektir. Ancak, yine de PQ'dan kaldırılacaklar.

yalancı kod

initialize graph 
initialize pq 
pq.insertAll(graph.getVertices()) 

while (pq is not empty) { 
    vertex = pq.remove() 
    edges = vertex.getEdges() 

    for all edges { 
    destination = edge.getDestination() 
    newDistance = edge.getLength() + vertex.getDistance() 
    if (newDistance < destination.getDistance()) { 
     destination.setShortestDistance(newDistance) 
     pq.update(destination) 
    } 
    } 
} 

MIT Açık Ders Malzemeleri Bağlantılar:
Path problems overview
Dijkstra