title: Dijkstra’s Algorithm for Adjacency List Representation + shortest path
body: <p>I'm writing program which check the shortest patch of graph, from selected vertex to the target and I have problem to display patch. Sometimes vertex have additional weight (like in code bellow variable currentWeight) when type of vertex is '2'. So I'm adding it in djikstra. When I'm setting currentWeight to 10 it's going well, but when I'm setting it to 2, it's giving me bad result. For example when input is :</p>
  
  <pre><code>5 2
  4 2 1 1 3 2
  2 2 0 1 2 1
  5 2 1 1 4 2
  0 2 0 2 4 3
  0 2 3 3 2 2
  </code></pre>
  
  <p>First two numbers : number of v, additional weight of vertex with type '2'</p>
  
  <p>Second line: type of vertex (4), number of destinies (2), destiny1 (1), weight of patch (1), destiny2 (3), weight of patch2 (2)</p>
  
  <p>Output should be:</p>
  
  <pre><code>0 1 2 
  </code></pre>
  
  <p>But now is :</p>
  
  <pre><code>0 3 2 4 
  </code></pre>
  
  <p>I don't know what is going wrong. Here is my code :</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;iostream&gt;
  #include &lt;conio.h&gt;
  #include &lt;limits.h&gt;
  
  using namespace std;
  
  
  
  struct graphNode {
      int weight;
      int v;
      graphNode *next;
  };
  
  class Graph {
  
  
  public:
      graphNode *head, *tail;
      int size;                   
      int  currentWeight;
      char type;                              
  
  
  
      void addNode(int v_temp, int v_weight) {
          graphNode *temp = new graphNode;
          temp-&gt;next = nullptr;
  
          if (head == nullptr) {
              temp-&gt;v = v_temp;
              temp-&gt;weight = v_weight;
              head = temp;
  
          }
          else {
              tail-&gt;next = temp;
              temp-&gt;v = v_temp;
              temp-&gt;weight = v_weight;
          }
  
          size++;
          tail = temp;
      }
  
  
      void setHome(char type, int timeKnight, int timeNi) {
  
          switch (type) {
          case '0':
              currentWeight = 0;
              break;
          case '1':
              currentWeight = 0;
              break;
          case '2':
              currentWeight = timeKnight;
              break;
          case '3':
              currentWeight = timeNi;
              break;
          case '4':
              currentWeight = 0;
              break;
          case '5':
              currentWeight = 0;
              break;
          }
      }
  
      void printGraph() {
          graphNode *temp = head;
  
          if (head != nullptr &amp;&amp; tail != nullptr) {
              while (temp) {
                  printf("%d(W: %d)  ", temp-&gt;v, temp-&gt;weight);
                  temp = temp-&gt;next;
              }
              printf("\n");
          }
      }
  
  
      // GET SET METHODS
  
  
      char returnType() {
          return type;
      }
  
      int returnCurrentSize() {
          return currentWeight;
      }
  
  
      int returnWeight(graphNode *temp) {
          return temp-&gt;weight;
      }
  
  
      void setType(char type_temp) {
          type = type_temp;
      }
  
      // Constructor
  
      Graph() {
          head = nullptr;
          tail = nullptr;
          size = 0;
          currentWeight = 0;
      }
  };
  
  
  struct heapNode {
      int v;
      int distance;
  
  
  };
  
  
  
  class Heap {
  private:
      Graph *graphArray;
      heapNode **heapArray;
      heapNode *root;
      int vNumber, size;
      int *position, *parent;
  
  public:
      heapNode *addEdge(int temp_v, int temp_distance) {
  
          heapNode *temp = new heapNode;
          temp-&gt;v = temp_v;
          temp-&gt;distance = temp_distance;
  
          return temp;
      }
  
  
      graphNode *returnVertexHead(int i) {
          return graphArray[i].head;
      }
  
      char returnType(int i) {
          return graphArray[i].returnType();
      }
  
  
      int returnWeight(int i) {
          return graphArray[i].returnCurrentSize();
      }
  
      bool isInHeap(int temp_v) {
          if (position[temp_v] &lt; vNumber) return true;
          return false;
      }
  
      bool isEmpty() {
          if (vNumber == 0) return true;
  
          return false;
      }
  
      void decrestDistans(int temp_v, int temp_distance) {
          int index = position[temp_v];
          heapNode *temp;
  
          heapArray[index]-&gt;distance = temp_distance;
  
  
          while (index &gt; 0 &amp;&amp; (heapArray[index]-&gt;distance &lt; heapArray[(index - 1) / 2]-&gt;distance)) {
  
              position[heapArray[index]-&gt;v] = (index - 1) / 2;
              position[heapArray[(index - 1) / 2]-&gt;v] = index;
  
              temp = heapArray[index];
  
  
              heapArray[index] = heapArray[(index - 1) / 2];
              heapArray[(index - 1) / 2] = temp;
  
              index = (index - 1) / 2;
          }
      }
  
  
      heapNode *removeMin() {
  
          if (vNumber == 0) return nullptr;
          root = heapArray[0];
          heapArray[0] = heapArray[vNumber - 1];
  
  
          position[root-&gt;v] = vNumber - 1;
          position[heapArray[vNumber - 1]-&gt;v] = 0;
  
          vNumber--;
  
          repairHeapDown(0);
          return root;
      }
  
      void repairHeapDown(int index) {
          heapNode *temp;
          int parent = index;
          int left = index * 2 + 1;
          int right = index * 2 + 2;
  
          if (left &lt;= vNumber &amp;&amp; heapArray[parent]-&gt;distance &gt; heapArray[left]-&gt;distance) parent = left;
          if (right &lt;= vNumber &amp;&amp; heapArray[parent]-&gt;distance &gt; heapArray[right]-&gt;distance) parent = right;
          if (index != parent) {
  
              position[heapArray[parent]-&gt;v] = index;
              position[heapArray[index]-&gt;v] = parent;
  
              temp = heapArray[index];
              heapArray[index] = heapArray[parent];
              heapArray[parent] = temp;
  
  
              repairHeapDown(index);
          }
      }
  
  
  
      void djikstra(int v_index) {
  
          int *distance = new int[vNumber];
          int i, v, weight;
          graphNode *current_graph;
          heapNode *current_heap;
  
          for (int i = 0; i &lt; vNumber; i++)
          {
              distance[i] = INT_MAX;
              heapArray[i] = addEdge(i, distance[i]);
              position[i] = i;
              parent[i] = 0;
  
          }
          parent[0] = 0;
          heapArray[v_index] = addEdge(v_index, distance[v_index]);
          position[v_index] = v_index;
          distance[v_index] = 0;
  
          cout &lt;&lt; v_index &lt;&lt; " ";
  
          decrestDistans(v_index, distance[v_index]);
  
  
          while (!isEmpty()) {
  
  
              current_heap = removeMin();
              i = current_heap-&gt;v;
  
  
              if (returnType(i) == '5') break;
  
  
              current_graph = returnVertexHead(i);
  
              while (current_graph != nullptr) {
  
                  v = current_graph-&gt;v;
                  weight = current_graph-&gt;weight + returnWeight(v);
  
                  if (isInHeap(v) &amp;&amp; distance[i] != INT_MAX &amp;&amp; ((weight + distance[i]) &lt; distance[v])) {
                      distance[v] = distance[i] + weight;
                      decrestDistans(v, distance[v]);
                      parent[i] = v;
                  }
  
  
                  current_graph = current_graph-&gt;next;
              }
  
  
          }
  
          printHeap(parent, v_index);
      }
  
  
  
  
      void printHeap(int temp_distance[], int v) {
  
          for (int i = 0; i &lt; size; i++)
          {
              if (temp_distance[i] != 0)
                  cout &lt;&lt; temp_distance[i] &lt;&lt; " ";
  
          }
      }
  
  
  
      Heap(Graph *table, int temp_vNumber) {
          vNumber = temp_vNumber;
          size = temp_vNumber;
          root = nullptr;
          heapArray = new heapNode*[temp_vNumber];
          position = new int[temp_vNumber];
          parent = new int[temp_vNumber];
          graphArray = table;
      }
  };
  
  
  
  int main() {
      int n, time_knight, patch_number, temp_v, temp_weight, i,
          home_index, gral_index, ni_index;
      char type;
  
      i = 0;
  
  
      cin &gt;&gt; n &gt;&gt; time_knight;
      Graph *table = new Graph[n];
  
      while (1) {
          cin &gt;&gt; type;
  
  
          table[i].setType(type);
          table[i].setHome(type, time_knight, 0);
  
          if (type == '4') home_index = i;
          if (type == '5') gral_index = i;
          if (type == '3') ni_index = i;
  
          cin &gt;&gt; patch_number;
          for (int j = 0; j &lt; patch_number; j++)
          {
              cin &gt;&gt; temp_v &gt;&gt; temp_weight;
              table[i].addNode(temp_v, temp_weight);
  
          }
  
          i++;
  
          if (i == n) break;
      }
  
      Heap *object = new Heap(table, n);
  
      object-&gt;djikstra(home_index);
  
  
      _getch();
  
      return 0;
  }
  </code></pre>