title: Dijkstra's algorithm on a graph represented by adjacency list
body: <p>I was implementing Dijkstra's algorithm on a weighted directed graph given by an adjacency list. While I get the distance being calculated correctly for nearly all vertices the very last vertex of the binary heap is causing some trouble. Another major issue is while I am making a node assign to an array of nodes the assignment isn't being executed, as when I printed the heap node values their distance were always INT_MAX. Please help me out!</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  #include&lt;limits.h&gt;
  
  long long int m=0;
  
  long long int parent(long long int i){
      return i/2;
  } 
  long long int left(long long int i){
      return (2*i);
  }
  long long int right(long long int i){
      return (2*i+1);
  }
  
  typedef struct edge{
      long long int src;
      long long int dest;
      long long int weight;
  }edge;
  
  typedef struct vertex{
      long long int id;
      long long int d;
      long long int pos;
  }node;
  
  void Decrease(node heap[],long long int i,node curr,node V[]){
      if(curr.d&gt;heap[i].d) return;
      heap[i]=curr;
      while(i&gt;=1 &amp;&amp; heap[parent(i)].d&gt;heap[i].d){
          V[i].pos=parent(i);
          V[parent(i)].pos=i;
          node temp=heap[parent(i)];
          heap[parent(i)]=heap[i];
          heap[i]=temp;
          i=parent(i);
      }
  }
  
  void heapify(node heap[],long long int i){
      long long int l=left(i);
      long long int r=right(i);
      long long int lowest;
      if(r&lt;=m &amp;&amp; heap[i].d&lt;heap[r].d){
          lowest=r;
      }
      else lowest=i;
      if(l&lt;=m &amp;&amp; heap[l].d&lt;heap[lowest].d){
          lowest=l;
      }
  
      if(lowest!=i){
          node temp=heap[lowest];
          heap[lowest]=heap[i];
          heap[i]=temp;
      }
  }
  
  node Extract(node heap[]){
       node min=heap[1];
       heap[1]=heap[m];
       m=m-1;
       heapify(heap,1);
       return min;
  }
  
  void Insert(node heap[],node curr,node V[]){
      m=m+1;  
      heap[m].d=INT_MAX;
      Decrease(heap,m,curr,V);
  }
  
  int main() {long long int N,S,D,C1,C2,D1,D2,W1,W2,W3,i,j;
      scanf("%lld %lld %lld %lld %lld %lld %lld %lld %lld 
      %lld",&amp;N,&amp;S,&amp;D,&amp;C1,&amp;C2,&amp;D1,&amp;D2,&amp;W1,&amp;W2,&amp;W3);
      edge** adj;
      adj=(edge**)malloc(sizeof(edge*)*N);
  
      long long int* deg;
      deg=(long long int*)malloc(sizeof(long long int)*(N+1));
      deg[0]=0;
  
      for(i=1;i&lt;=N;i++){
          deg[i]=(i*C2+i*i*D2)%(D);
          adj[i]=(edge*)malloc(sizeof(edge)*(deg[i]+1));
          for(j=1;j&lt;=deg[i];j++){
              edge temp;
              temp.dest=(i*C1+j*D1)%(N);
              temp.dest=temp.dest+1;
              temp.weight=(i*W1+j*W2)%(W3);
              temp.src=i;
              adj[i][j]=temp;
          }
      }
  
      node* V;
      V=(node*)malloc(sizeof(node)*(N+1));
      for(i=0;i&lt;=N;i++){
          V[i].d=INT_MAX;
          V[i].id=i;
      }
      V[S].d=0;
  
      node* heap;
      heap=(node*)malloc(sizeof(node)*(N));
  
      for(i=1;i&lt;=N;i++){
          Insert(heap,V[i],V);
      }
  
      while(m&gt;-1){
          node temp=Extract(heap);
          int i=temp.id;
          for(j=1;j&lt;=deg[i];j++){
              edge w=adj[i][j];
              if(V[w.dest].d&gt;V[i].d+w.weight){
                  V[w.dest].d=V[i].d+w.weight;
                  Decrease(heap,V[w.dest].pos,V[w.dest],V);
              }
          }
          /*for(long long int z=1;z&lt;=m;z++){
             printf("%lld %lld   ",heap[z].id,heap[z].d);
          }*/
      }
      /*for(i=1;i&lt;=N;i++){
          printf("%lld %lld\n",V[i].id,V[i].d);
      }*/
      return 0;
  </code></pre>
  
  <p>}</p>