title: Shortest path with Bellman & Ford algorithm
body: <p>I want to implement Shortest path with Bellman &amp; Ford algorithm. my idea is I use adjacent matrix</p>
  <p>to save the information of digraph. If I want to find the shorest path of vertex i ,then I observe in-</p>
  <p>degree of vertex i by the ith column of adjacent matrix ,and I save the shortest value of ith column</p>
  <p>to a variable <strong>&quot;min&quot;</strong>.if I want to find the shorest path from source vertex v to vertex i.</p>
  <p>I only <strong>compare distance[i] with (distance[j]+ min )</strong>, because &quot;min&quot; is equal to adjmatrix[j][i].</p>
  <p>In addition, I make the traverse(source, k) function to comfirm which vertex we can reach it in k</p>
  <p>steps and use the data structure stack to save information of vertex i. I assume to that i'll get  all the</p>
  <p>shortest path from source vertex v to every vertex o graph except v itself. But the consequence after</p>
  <p>compiling isn't that I expected. I finally got distance[i], 0 &lt;= i &lt; MAX_VERTEX, 1000,-1, 5, 5, 0 ,1000,</p>
  <p>1000, respectively. What is my problem? Thanks for answer.</p>
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  
  #define MAX_VERTEX 7
  #define FALSE 0
  #define TRUE 1
  #define MAX_DISTANCE_LIMIT 1000
  #define MAX_STACK_LENGTH 100
  
  #define MIN(x, y) ((x) &lt; (y) ? x : y)
  
  int stack[MAX_STACK_LENGTH];
  int top = -1; //pointer to top of stack.  
  int adjmatrix[MAX_VERTEX][MAX_VERTEX];
  short found[MAX_VERTEX];  //traverse(v ,k) : reach the vertex i By taking the k steps at most  
  int distance[MAX_VERTEX]; //save the shortest path that source v to every vertex i
  
  int init_matrix(void);
  void BellmanFord(int v); //v is source
  void traverse(int v,int times);
  void push(int vertex);
  int pop(void);
  
  int main(void){
      
      int i,j;
      
      init_matrix(); //initial matrix and found[] array
      
      for(i = 0; i &lt; MAX_VERTEX; i++){
          for(j = 0; j &lt; MAX_VERTEX; j++)
              printf(&quot;%2d &quot;, adjmatrix[i][j]);
          printf(&quot;\n&quot;);
      }
      printf(&quot;--------------------------------------------------\n&quot;);
      
      BellmanFord(0);
      
      for(i = 0; i &lt; MAX_VERTEX; i++)
          printf(&quot;%4d &quot;, i);
      printf(&quot;\n&quot;);
          
      for(i = 0; i &lt; MAX_VERTEX; i++)
          printf(&quot;%4d &quot;, distance[i]);
      
      return 0;
  }
  
  int init_matrix(void){
      int num_edge = 0, i, j, w;
      
      for(i = 0; i &lt; MAX_VERTEX; i++){
          found[i] = FALSE;
          for(j = 0; j &lt; MAX_VERTEX; j++)
              adjmatrix[i][j] = MAX_DISTANCE_LIMIT; //set a large value to the entry of the vertice which aren't adjacent
      }
      
      while(1){
          printf(&quot;enter the vertices and weight of edge connected between them(w,tail,head): &quot;);
          scanf(&quot;%d%d%d&quot;, &amp;w, &amp;i, &amp;j);
          if((i &gt;= MAX_VERTEX) || (j &gt;= MAX_VERTEX)){
              fprintf(stderr, &quot;index if the matrix should be less than %d&quot;);
              exit(EXIT_FAILURE);
          }
          if(w == 0) break;
          
          adjmatrix[i][j] = w;
          num_edge++;
      }
      return num_edge;
  }
  
  void BellmanFord(int v){//compute all shortest path from v to every vertex ,and allow edge is negative
      int i, k, min = MAX_DISTANCE_LIMIT, j, minpos;
      for(int i = 0; i &lt; MAX_VERTEX; i++)
          distance[i] = adjmatrix[v][i]; //value of dist&quot;1&quot;
      
      for(k = 2; k &lt;= MAX_VERTEX - 1; k++){
          traverse(v,k); //traverse(v ,k)will set found[i] that we can reach in k steps TRUE.
          for(i = 0; i &lt; MAX_VERTEX; i++ ){
              if( found[i] == FALSE)
                  continue;
              for(j = 0; j &lt; MAX_VERTEX; j++)
                  if(adjmatrix[j][i]+distance[j] &lt; min) {
                      min = adjmatrix[j][i]+distance[j];
                      minpos = j;
                  }
              distance[i] = MIN(distance[i],adjmatrix[minpos][i]+distance[j]);
          }
          for(i = 0; i &lt; MAX_VERTEX; i++ ) //initial found array to FALSE
              found[i] = FALSE;
      }
  }
  void traverse(int v,int times){
      int i, next_order ,count = 0;
      
      if (times == 0) return ;
      
      for(i = 0; i &lt; MAX_VERTEX; i++){
          if((adjmatrix[v][i] != MAX_DISTANCE_LIMIT) &amp;&amp; (!found[i])){
              found[i] = TRUE;
              if(times == 1)
                  return;
              push(i);
              count++;
          }
      }
      for(i = 0; i &lt; count; i++){
          next_order = pop();
          traverse(next_order,times-1);
      }
  
      return;
  }
  
  void push(int vertex){
      if(top &gt;= MAX_STACK_LENGTH){
          fprintf(stderr, &quot;The stack is full.&quot;);
          exit(EXIT_FAILURE);
      }
      stack[++top] = vertex;
  }
  int pop(void){
      if(top == -1){
          fprintf(stderr, &quot;The stack is empty.\n&quot;);
          exit(EXIT_FAILURE);
      }
      else
          return stack[top--];
  }
  
  /************************************
  *graph information (w,tail,head)
  input
  6 0 1
  5 0 2
  5 0 3
  -1 1 4
  1 2 4
  -2 2 1
  -2 3 2
  -1 3 5
  3 5 6
  3 4 6
  0 0 0 //end the input
  ************************************
  adjmatrix:
  
  0  6  5  5  0  0  0
  0  0  0  0 -1  0  0
  0 -2  0  0  1  0  0
  0  0 -2  0  0 -1  0
  0  0  0  0  0  0  3
  0  0  0  0  0  0  3
  0  0  0  0  0  0  0
  
  **************************************/
  </code></pre>