Algorytm Dijkstry z kolejką o priorytecie min

Question

Próbuję zaimplementować algorytm dijkstra z kolejką priorytetową, ale nie mogę zrozumieć, jak to działa. Czytam wiele przewodników w Internecie, ale w ogóle nie rozumiem tego algorytmu.

Moje pytanie brzmi: jaki jest priorytet każdego węzła? Myślę, że jest to ciężar przychodzącej krawędzi z minimalną wartością, ale nie jestem pewien. Czy to prawda?

Drugie pytanie, kiedy wyodrębniam źródło kolejki, jak działa, jeśli ten węzeł nie jest przyległy do ​​żadnego z odwiedzanych węzłów?

Answer 1

Powinieneś użyć priority queue, gdzie z najkrótszą odległością od początkowej vertex uzyska najwyższy priorytet. Początkowo wszystkie vertices będzie miał najmniejszą odległość nieskończoności i wyjściowymi vertex będzie mieć najkrótszej odległości 0.

początkową, wstawienie wszystkich vertices (z jego edges) z wykresu wewnątrz PQ. Usuń vertex z PQ i odkryj wszystkie jego edges. Porównaj najkrótsze odległości ze wszystkimi sąsiednimi vertices, a jeśli jakakolwiek odległość jest mniejsza niż najkrótsza odległość od bieżącego vertex, zaktualizuj sąsiednią vertex najkrótszą odległość wewnątrz PQ. Kontynuuj, gdy PQ nie jest pusta. Vertices który nie uzyskał edges zakończy się najkrótszą odległością nieskończoności, ponieważ nie jest możliwe 'dostać się do nich' od początkowego vertex. Będą one jednak nadal usuwane z PQ.

Pseudokod

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 OpenCourseWare Linki:
Path problems overview
Dijkstra