title: Do we really need the "visited or not" info of a vertex in Dijkstra's algorithm?
body: <p>In  <a href="https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&amp;oldid=626530538#Using_a_priority_queue" rel="nofollow">Dijkstra's algorithm on Wikipedia (older version, now corrected by me)</a>, the implementation with priority queue will check <code>vertex</code> is visited or not before check the shorter path.</p>
  
  <p>Is it really necessary? or even correct?</p>
  
  <pre><code>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 &lt; dist[v]
                       dist[v] ← alt
                       prev[v] ← u
                       Q.decrease_priority(v,alt)
                   end if
               end if
           end for
       end while
       return prev[]
  </code></pre>
  
  <p>I think checking <code>v is scanned already or not</code> will prevent any chances in the future if <code>v</code>'s path need to be updated.</p>
  
  <hr>
  
  <p>Update:</p>
  
  <p>I've edited the page and the <a href="https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&amp;oldid=646408018#Using_a_priority_queue" rel="nofollow">current Dijkstra's algorithm wiki page</a> is now correct.</p>