title: Correctness of Bellman-Ford Algorithm, can we still do better?
body: <p>I learned that the Bellman-Ford Algorithm has a running time of O(|E|*|V|), in which the E is the number of edges and V the number of vertices. Assume the graph does not have any negative weighted cycles.</p>
  
  <p>My first question is that how do we prove that within (|V|-1) iterations (every iteration checks every edge in E), it updates the shortest path to every possible node, given a particular start node? Is it possible that we have iterated (|V|-1) times but still not ending up with shortest paths to every node? </p>
  
  <p>Assume the correctness of the algorithm, can we actually do better than that? It occurs to me that not all edges are negatively weighted in a particular graph. The Bellman-Ford Algorithm seems expensive, as every iteration it goes through every edges.</p>