CODEWITHSUNDEEP
algorithmdata-structuresgraphdijkstrashortest-path
Jackson Tale
Jackson Tale

Reputation: 25842

Do we really need the "visited or not" info of a vertex in Dijkstra's algorithm?

In Dijkstra's algorithm on Wikipedia (older version, now corrected by me), the implementation with priority queue will check vertex is visited or not before check the shorter path.

Is it really necessary? or even correct?

function Dijkstra(Graph, source):
      dist[source] ← 0                      // Initialization
      for each vertex v in Graph:           
          if v ≠ source
              dist[v] ← infinity            // Unknown distance from source to v
              prev[v] ← undefined           // Predecessor of v
          end if
          Q.add_with_priority(v,dist[v])
      end for 


     while Q is not empty:               // The main loop
         u ← Q.extract_min()               // Remove and return best vertex
         mark u as scanned
         for each neighbor v of u:
             if v is not yet scanned: // **is this in need?**
                 alt = dist[u] + length(u, v) 
                 if alt < dist[v]
                     dist[v] ← alt
                     prev[v] ← u
                     Q.decrease_priority(v,alt)
                 end if
             end if
         end for
     end while
     return prev[]

I think checking v is scanned already or not will prevent any chances in the future if v's path need to be updated.

Update:

I've edited the page and the current Dijkstra's algorithm wiki page is now correct.

Upvotes: 1

Views: 1051

Answers (2)

Ulrich Eckhardt
Ulrich Eckhardt

Reputation: 17434

The flag is not needed. Just look at this section of pseudocode:

if v is not yet scanned:
    alt = dist[u] + length(u, v) 
    if alt < dist[v]
         dist[v] ← alt
         prev[v] ← u
         Q.decrease_priority(v,alt)
    end if
end if

If you check the different parts:

  • alt seems to be a local variable that is only used as temporary here, so writing to it doesn't make any difference anywhere else.
  • If v was already removed from the queue, the path to it was at most as long as the path to u, otherwise u would have been extracted first.
  • If v was visited, then dist[v] <= dist[u] <= alt. In that case the comparison alt < dist[v] is false and the rest of the code is skipped anyways.

Just to explain a bit more, think about the role of the priority queue. It contains the nodes, ordered by the shortest known path to them. When extracting a node from the queue, all nodes before where at most as far away as that node and all nodes after will be at least as far away as that node. Since all nodes that were closer were already processed, any new path discovered to one of these nodes there will be via a node that is at least as far away. This means that there can't be any shorter route to an extracted node coming from a node that is still in the queue, so the mere check alt < dist[v] will already exclude those nodes that were scanned.

Upvotes: 3

sujai M J
sujai M J

Reputation: 1301

It is require to check V is scanned already or not.

At first cycle we find the vertex(V1) which is minimum cost of neighbor vertexes of source vertex(S1).

At Second cycle, we should not reverse back to the source vertex(S1) from vertex(V1).

Reverse back to the source Vertex (S1) occurs when length(S1,V1) is minimum of neighbor cost vertex(V1).

Code without checking V scanned or not will result in loop for certain case.

Upvotes: -2

Related Questions