title: Bellman Ford Algorithm Explanation
body: <p>I read the Bellman Ford Algorithm. What I couldn't understand is why is there a loop which runs for |V|-1 times (the upper loop in the following segment).</p>
  
  <pre><code>for ( i = 1; i &lt;= V-1; i++)
  {
      for (j = 0; j &lt; E; j++)
      {
          int u = graph-&gt;edge[j].src;
          int v = graph-&gt;edge[j].dest;
          int weight = graph-&gt;edge[j].weight;
          if (dist[u] != INT_MAX &amp;&amp; dist[u] + weight &lt; dist[v])
          {
              dist[v] = dist[u] + weight;
  
          }
      }
  </code></pre>
  
  <p>I went through several tutorials. All are saying the same thing that  There can be maximum |V| – 1 edges in any simple path, that is why the outer loop runs |v| – 1 times. The idea is, assuming that there is no negative weight cycle, if we have calculated shortest paths with at most i edges, then an iteration over all edges guarantees to give shortest path with at-most (i+1) edges.</p>
  
  <p>So, when i=1, the distances I calculated after the relaxation method, are those the shortest distances from the source ?</p>
  
  <p>Please explain this...</p>