title: Given directed weighted graph that has one negeative edge (u,v), find shortest path (s,t)
body: <p><strong>Given:</strong> Directed, weighted graph G(V,E) and <code>s,t</code> are vertices of <code>V</code>, all edges are positive except the edge <code>(u,v)</code> which is negative.</p>
  
  <p><strong>Problem:</strong> Find the shortest path (<strong>Meaning: with the least weight</strong>) from s to t.</p>
  
  <p><strong>My solution:</strong> Well, because we have a negative edge we should use Bellman-Ford's algorithm. Doing <code>n-1</code> "relax" on the edges, and if there's a problem in the <code>n</code>'th iteration there's a cycle - thus return false. otherwise, return the shortest path from <code>s</code> to <code>t</code>.</p>
  
  <p><strong>Another solution:</strong> Using Dijkstra, and changing it a bit by saving d(u) and passing on the negative edge (u,v) and doing "relax", then we go again on all the edges without the negative edge, if the distances were changed, we have a cycle, otherwise all good and return the shortest path.</p>
  
  <p><strong>Note:</strong> I'm obviously not sure about my solution, the fact that there is one negative edge is tricky, any ideas?</p>
  
  <p>Note2: To make it interesting, <strong>you cannot use Bellman-Ford</strong>.</p>