title: Can you use Dijkstra's algorithm if there is a negative weight so long as there are no cycles?
body: <p><strong>Update</strong>:  I really botched the original question.  My original title was "Why do we first do a topological sort for acyclic weighted digraph shortest path problems?" but my question content was about Dijkstra's algorithm.  Hopefully since I've changed the title, the question is updated in such a way that it is useful to someone else. The answer to the updated question title is "<strong>yes</strong>".</p>
  
  <p><strong>Original question</strong>:</p>
  
  <p>Why do I need to do a topological sort first? <a href="http://algs4.cs.princeton.edu/44sp/AcyclicSP.java.html" rel="nofollow">(see code here)</a>  Can't I just use Dijkstra's algorithm shown below and avoid the topological sort altogether (little messy syntax-wise but you get the idea)</p>
  
  <pre><code>MinIndexedPriorityQueue waitingEdges = new MinIndexedPriorityQueue
  Graph g //some weighted directed graph
  double[] distTo = new double[g.vertexCount]
  Edge[] edgeTo = new Edge[g.vertexCount]
  int source = //init to some value
  
  void minPathInit()
      init distTo to double.MAX_VALUE
      //init first node
      distTo [source] = 0
      visit(source)
      while waitingEdges.count&gt;0
          int vertex = waitingEdges.dequeue()
          relax(vertex )
  
  void relax(v) //note that visit has been renamed to relax
      for each edge in graph.getEdgesFrom(v)
          int to= edge.to
          if edge.weight + distTo [edge.from]&lt;  distTo [to]
              distTo[to] = edge.weight + distTo [edge.from]
              edgeTo[to] = edge
              if waitingEdges.contains(to)
                  waitingEdges.change(to,  distTo[to] )
              else
                  waitingEdges.enqueue(to,  distTo[to] )
  
  
  //after everything is initialized
  getPathTo(v)
      if not hasBeenVisited[v]
          return null
      Stack path = new Stack
      while edgeTo[v] != source
          path.push(edgeTo[v])
          v = edgeTo[v].from
      return path
  </code></pre>
  
  <p>I can understand why Dijkstra's algorithm can't handle negative cycles (because it would get stuck in an infinite loop) but if there are no negative cycles, why does it fail as shown (and require the topological sort first)</p>
  
  <p><strong>Update:</strong> Ok, I can see that I've botched up this question so I will try to fix it up a bit with an update.  Thanks for taking the time to point the hole's out for me.  I mistakenly thought <a href="http://algs4.cs.princeton.edu/44sp/AcyclicSP.java.html" rel="nofollow">AcyclicSP</a> becomes Dijkstra's algorithm when removing the topological sort which is not the case.</p>
  
  <p>However, my question about Dijkstra's algorithm (using the version shown above) remains.  Why can't it be used even if there is a negative weight so long as there are no cycles?  There is a java version of <a href="http://algs4.cs.princeton.edu/44sp/DijkstraSP.java.html" rel="nofollow">Dijkstra's algorithm here</a>.  Mine is very similar to this (since this guy's book is where I learned about it) but his example is probably easier to read for some of you.</p>