Dijkstra algorithm with min-priority queue

dijkstra, graph, path, priority-queue, shortest-path

Solution

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

Problem

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 questions are: What is the priority for each node? I think that it is the weight of the incoming edge with the minimum value, but I'm not sure. Is this true? Second question, when I extract the root of the queue, how does it work if this node is not adjacency with no one of the visited nodes?

Original source