title: Can we change Dijkstra's Algorithm to work with negative weights?
body: <p>The pseudocode  as taken from Wikipedia:  </p>
  
  <pre><code>function Dijkstra(Graph, source):
   2      for each vertex v in Graph:                                // Initializations
   3          dist[v] := infinity ;                                  // Unknown distance function from source to v
   4          previous[v] := undefined ;                             // Previous node in optimal path from source
   5      end for ;
   6      dist[source] := 0 ;                                        // Distance from source to source
   7      Q := the set of all nodes in Graph ;                       // All nodes in the graph are unoptimized - thus are in Q
   8      while Q is not empty:                                      // The main loop
   9          u := vertex in Q with smallest distance in dist[] ;    // Start node in first case
  10          if dist[u] = infinity:
  11              break ;                                            // all remaining vertices are inaccessible from source
  12          end if ;
  13          remove u from Q ;
  14          for each neighbor v of u:                              // where v has not yet been removed from Q.
  15              alt := dist[u] + dist_between(u, v) ;
  16              if alt &lt; dist[v]:                                  // Relax (u,v,a)
  17                  dist[v] := alt ;
  18                  previous[v] := u ;
  19                  decrease-key v in Q;                           // Reorder v in the Queue
  20              end if ;
  21          end for ;
  22      end while ;
  23      return dist[] ;
  24  end Dijkstra.
  </code></pre>
  
  <p>Now, in line 14 we see that the relaxation is applied only on neighbors of <code>u</code> that have not yet been removed from <code>Q</code>. But if we take also neighbors of <code>u</code> that have been removed from <code>Q</code>, it seems to me that the algorithm <strong>does</strong> work with negative weights. I haven't found any instance that contradicts this claim.</p>
  
  <p>So why Dijkstra's Algorithm isn't altered this way?</p>