Dijkstra algorithm with min-priority queue

问题:

I'm trying to implement the dijkstra algorithm with priority queue, but I can't understand how it works. I read many guide on the web but I can't understand this algorithm at all.

My question are: what is the priority for each node? I think that it is the weight of the incoming edge with minimun value, but I'm not sure. Is this true?

Second question, when I extract the root of the queue, how works if this node is not adjacency with no one of the visited nodes?

回答1:

You should use priority queue where the vertex with the shortest distance from the starting vertex will get the highest priority. Initially, all vertices will have the shortest distance of infinity and the starting vertex will have the shortest distance 0.

Start by inserting of all vertices (with its edges) from the graph inside the PQ. Remove vertex from the PQ and explore all its edges. Compare the shortest distances with all adjacent vertices and if any distance is less than the shortest distance on the current vertex, update adjacent vertex shortest distance inside the PQ. Continue while PQ is not empty. Vertices which got no edges will finish with the shortest distance of infinity because it is not possible 'get to them' from the starting vertex. However, they will be still removed from the PQ.

Pseudocode

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