title: Modifying the Dijkstra Code to print the path
body: <p>I got this Dijkstra code for graph using adjacency list, but I am having trouble to modify it to show the minimum path. Any help? I need the vector of predecessors to calculate the betweenness and the closeness to each vertex.</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;limits.h&gt;
  
  struct AdjListNode
  {
      int dest;
      int weight;
      struct AdjListNode* next;
  };
  
  struct AdjList
  {
      struct AdjListNode *head;  // pointer to head node of list
  };
  
  struct Graph
  {
      int V;
      struct AdjList* array;
  };
  
  struct AdjListNode* newAdjListNode(int dest, int weight)
  {
      struct AdjListNode* newNode =
              (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
      newNode-&gt;dest = dest;
      newNode-&gt;weight = weight;
      newNode-&gt;next = NULL;
      return newNode;
  }
  
  struct Graph* createGraph(int V)
  {
      struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
      graph-&gt;V = V;
  
      // Create an array of adjacency lists.  Size of array will be V
      graph-&gt;array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
  
       // Initialize each adjacency list as empty by making head as NULL
      for (int i = 0; i &lt; V; ++i)
          graph-&gt;array[i].head = NULL;
  
      return graph;
  }
  
  void addEdge(struct Graph* graph, int src, int dest, int weight)
  {
      // Add an edge from src to dest.  A new node is added to the adjacency
      // list of src.  The node is added at the begining
      struct AdjListNode* newNode = newAdjListNode(dest, weight);
      newNode-&gt;next = graph-&gt;array[src].head;
      graph-&gt;array[src].head = newNode;
  
      // Since graph is undirected, add an edge from dest to src also
      newNode = newAdjListNode(src, weight);
      newNode-&gt;next = graph-&gt;array[dest].head;
      graph-&gt;array[dest].head = newNode;
  }
  
  struct MinHeapNode
  {
      int  v;
      int dist;
  };
  
  struct MinHeap
  {
      int size;      // Number of heap nodes present currently
      int capacity;  // Capacity of min heap
      int *pos;     // This is needed for decreaseKey()
      struct MinHeapNode **array;
  };
  
  struct MinHeapNode* newMinHeapNode(int v, int dist)
  {
      struct MinHeapNode* minHeapNode =
             (struct MinHeapNode*) malloc(sizeof(struct MinHeapNode));
      minHeapNode-&gt;v = v;
      minHeapNode-&gt;dist = dist;
      return minHeapNode;
  }
  
  struct MinHeap* createMinHeap(int capacity)
  {
      struct MinHeap* minHeap =
           (struct MinHeap*) malloc(sizeof(struct MinHeap));
      minHeap-&gt;pos = (int *)malloc(capacity * sizeof(int));
      minHeap-&gt;size = 0;
      minHeap-&gt;capacity = capacity;
      minHeap-&gt;array =
           (struct MinHeapNode**) malloc(capacity * sizeof(struct MinHeapNode*));
      return minHeap;
  }
  
  void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)
  {
      struct MinHeapNode* t = *a;
      *a = *b;
      *b = t;
  }
  
  void minHeapify(struct MinHeap* minHeap, int idx)
  {
      int smallest, left, right;
      smallest = idx;
      left = 2 * idx + 1;
      right = 2 * idx + 2;
  
      if (left &lt; minHeap-&gt;size &amp;&amp;
          minHeap-&gt;array[left]-&gt;dist &lt; minHeap-&gt;array[smallest]-&gt;dist )
        smallest = left;
  
      if (right &lt; minHeap-&gt;size &amp;&amp;
          minHeap-&gt;array[right]-&gt;dist &lt; minHeap-&gt;array[smallest]-&gt;dist )
        smallest = right;
  
      if (smallest != idx)
      {
          MinHeapNode *smallestNode = minHeap-&gt;array[smallest];
          MinHeapNode *idxNode = minHeap-&gt;array[idx];
  
          minHeap-&gt;pos[smallestNode-&gt;v] = idx;
          minHeap-&gt;pos[idxNode-&gt;v] = smallest;
  
          swapMinHeapNode(&amp;minHeap-&gt;array[smallest], &amp;minHeap-&gt;array[idx]);
  
          minHeapify(minHeap, smallest);
      }
  }
  
  int isEmpty(struct MinHeap* minHeap)
  {
      return minHeap-&gt;size == 0;
  }
  
  struct MinHeapNode* extractMin(struct MinHeap* minHeap)
  {
      if (isEmpty(minHeap))
          return NULL;
  
      struct MinHeapNode* root = minHeap-&gt;array[0];
  
      struct MinHeapNode* lastNode = minHeap-&gt;array[minHeap-&gt;size - 1];
      minHeap-&gt;array[0] = lastNode;
  
      minHeap-&gt;pos[root-&gt;v] = minHeap-&gt;size-1;
      minHeap-&gt;pos[lastNode-&gt;v] = 0;
  
      --minHeap-&gt;size;
      minHeapify(minHeap, 0);
  
      return root;
  }
  
  void decreaseKey(struct MinHeap* minHeap, int v, int dist)
  {
      int i = minHeap-&gt;pos[v];
  
      minHeap-&gt;array[i]-&gt;dist = dist;
  
      while (i &amp;&amp; minHeap-&gt;array[i]-&gt;dist &lt; minHeap-&gt;array[(i - 1) / 2]-&gt;dist)
      {
          minHeap-&gt;pos[minHeap-&gt;array[i]-&gt;v] = (i-1)/2;
          minHeap-&gt;pos[minHeap-&gt;array[(i-1)/2]-&gt;v] = i;
          swapMinHeapNode(&amp;minHeap-&gt;array[i],  &amp;minHeap-&gt;array[(i - 1) / 2]);
  
          i = (i - 1) / 2;
      }
  }
  
  bool isInMinHeap(struct MinHeap *minHeap, int v)
  {
     if (minHeap-&gt;pos[v] &lt; minHeap-&gt;size)
       return true;
     return false;
  }
  
  void printArr(int dist[], int n)
  {
      printf("Vertex   Distance from Source\n");
      for (int i = 0; i &lt; n; ++i)
          printf("%d \t\t %d\n", i, dist[i]);
  }
  
  void dijkstra(struct Graph* graph, int src)
  {
      int V = graph-&gt;V;// Get the number of vertices in graph
      int dist[V];      // dist values used to pick minimum weight edge in cut
  
      struct MinHeap* minHeap = createMinHeap(V);
  
      for (int v = 0; v &lt; V; ++v)
      {
          dist[v] = INT_MAX;
          minHeap-&gt;array[v] = newMinHeapNode(v, dist[v]);
          minHeap-&gt;pos[v] = v;
      }
  
      minHeap-&gt;array[src] = newMinHeapNode(src, dist[src]);
      minHeap-&gt;pos[src]   = src;
      dist[src] = 0;
      decreaseKey(minHeap, src, dist[src]);
  
      minHeap-&gt;size = V;
  
      while (!isEmpty(minHeap))
      {
          struct MinHeapNode* minHeapNode = extractMin(minHeap);
          int u = minHeapNode-&gt;v; // Store the extracted vertex number
  
          struct AdjListNode* pCrawl = graph-&gt;array[u].head;
          while (pCrawl != NULL)
          {
              int v = pCrawl-&gt;dest;
  
              if (isInMinHeap(minHeap, v) &amp;&amp; dist[u] != INT_MAX &amp;&amp; 
                                            pCrawl-&gt;weight + dist[u] &lt; dist[v])
              {
                  dist[v] = dist[u] + pCrawl-&gt;weight;
                  decreaseKey(minHeap, v, dist[v]);
              }
              pCrawl = pCrawl-&gt;next;
          }
      }
      printArr(dist, V);
  }
  </code></pre>