Required to use PriorityQueue to implements Dijkstra’s algorithm for solving the single-source shortest-path problem for weighted graphs without negative edge weights. I have a wrong output of my program.
Here's the code:

//Graph.h
class Graph
{

 public:
    
  Graph(int r = 1, int c = 1); // constructor
  void setCost(int v_1, int v_2, int weight); // sets the cost of an edge
  int getCost(int v_1, int v_2); // gets the cost of an edge

 private:

  int **ptr; 
  int rows;
  int columns;

};

//Graph.cpp
#include "Graph.h"
#include <iostream>
using namespace std;

Graph::Graph(int r, int c) // constructor; creates an instance of the graph class
{
  int i, j;
  rows = r;
  columns = c;
  ptr = new int*[rows];
  for (i = 0; i < rows; i++)
    {  
      ptr[i] = new int[columns];
    }
  for (i = 0; i < rows; i++)
    {
      for (j = 0; j < columns; j++)
    {
      ptr[i][j] = 0;
    }
    }      
}

void Graph::setCost(int v_1, int v_2, int weight) // sets the cost of an edge
{  
  ptr[v_1][v_2] = weight;
}

int Graph::getCost(int v_1, int v_2) // gets the cost of an edge
{
  return ptr[v_1][v_2];
}

//PriorityQueue.h
class PriorityQueue
{
 public:

  PriorityQueue(int nodes, int source); // constructor
  void Heapify(int index); // heapifies so the minimum is at the top
  int ExtractMin(); // returns the node with the minimum distance
  bool IsEmpty(); // checks to see if the priority queue is empty
  int *A;
  int *distance;
  int n;
};

//PriorityQueue.cpp
#include "PriorityQueue.h"
#include <iostream>
using namespace std;

PriorityQueue::PriorityQueue(int nodes, int source) // constructor; creates an instance of the priority queue class
{
  int i;
  n = nodes; 
  A = new int[n + 1];
  distance = new int[n + 1];  
  for(i = 1; i <= n; i++)
    {      
      A[i] = i - 1;
      if((i - 1) == source) distance[i] = 0;      
      else distance[i] = 10000;
    }
  for(i = n / 2; i > 0; i--)
    {      
      Heapify(i);    
    }
}

void PriorityQueue::Heapify(int index) // heapifys the priority queue so the minimum distance is at the top
{
  int i, min_child_index, temp_1, temp_2;
  while(index <= n / 2)
    {
      if(distance[2 * index] <= distance[2 * index + 1]) min_child_index = 2 * index;
      else min_child_index = 2 * index + 1;
      if(distance[index] > (distance[min_child_index])) {
        temp_1 = distance[index];
    temp_2 = A[index];
    distance[index] = distance[min_child_index];
        A[index] = A[min_child_index];
    distance[min_child_index] = temp_1;
    A[min_child_index] = temp_2;
        index = min_child_index;
      } else {
        return;
      }
    }
}

int PriorityQueue::ExtractMin() // returns the node with the minimum distance
{
  int min;
  min = A[1];
  A[1] = A[n];
  distance[1] = distance[n]; 
  n = n - 1;
  Heapify(1);
  return min;
}
bool PriorityQueue::IsEmpty() // checks to see if the priority queue is empty
{
  if(n == 0) return true; 
  else return false;
}


//main.cpp
#include <iostream>
#include "Graph.cpp"
#include "PriorityQueue.cpp"
using namespace std;

void PrintPath(int node, int p_a[], int s); // PrintPath function

int main() {

  int num_nodes, num_edges, i, source, parent, cost, total_cost, vertex_1, vertex_2, j, temp_parent;

  cin >> num_nodes; // inputs the number of nodes

  Graph g(num_nodes, num_nodes); // creates a corresponding instance of the Graph class

  int* parent_a = new int[num_nodes]; // creates an array to store the parent of each node

  int* cost_a = new int[num_nodes]; // creates an array to store the cost of each node

  for(i = 0; i < num_nodes; i++) 
    {
      parent_a[i] = -1; // initializes each element of the parent array to -1
      cost_a[i] = 0; // initializes each element of the cost array to 0   
    }

  cin >> num_edges; // inputs the number of edges
  
  for(i = 0; i < num_edges; i++)
    {
      cin >> vertex_1;
      cin >> vertex_2;
      cin >> cost;
      g.setCost(vertex_1, vertex_2, cost); // stores the edges between nodes in the graph
    }
  cin >> source; // inputs the source
  PriorityQueue p(num_nodes, source); // creates an instance of the priority queue class
  while(!p.IsEmpty()){ // while the priority queue is  not empty
    parent = p.ExtractMin(); // dequeues the node with the shortest path from the source
    for (i = 0; i < num_nodes; i++)
      {
    cost = g.getCost(parent, i); // gets the cost of the edge between the parent and i    
    if (cost != 0) // if the cost isn't 0 there is an edge
      {     
        if (parent_a[i] != -1) // if i has a parent
          {        
        for (j = 1; j <= p.n; j++)
        {
          if (p.A[j] == i) p.distance[j] += cost; // add the cost of the edge to the
                                                  //  distance array
        }    
          } else { // if i does not have a parent
          cost_a[i] = cost; // put the cost in the cost array
          parent_a[i] = parent; // put the parent in the parent array 
          for (j = 1; j <= p.n; j++)
        {
          if (p.A[j] == i) p.distance[j] = cost; // put the cost in the distance array
        }
        }
      }
      }
    for(i = p.n / 2; i > 0; i--)
    {      
      p.Heapify(i); // heapify the priority queue with the updated distances
    }
  }

  // output
  for (i = 0; i < num_nodes; i++) 
    {     
      cout << i << ": ";
      if (i == source) cout << i << " cost of 0" << endl;    // if i is the source
      else PrintPath(i, parent_a, source); // if i is not the source, call PrintPath function
      for (j = 1; j <= p.n; j++)
    {
      if (p.A[j] == i) cout <<  p.distance[j] << endl;
    }     
    }
  return 0;
}

// PrintPath function
// This function prints the path of nodes that are not the source along with their 
// costs/ distances.
void PrintPath(int node, int p_a[], int s)
{
  if (p_a[node] == s) cout << s << "-" << node;
  else PrintPath(p_a[node], p_a, s); 
  cout << "-" << node << " cost of ";
}

Here is a sample input:
7 12
0 1 2
0 3 1
1 3 3
1 4 10
2 0 4
2 5 5
3 2 2
3 4 2
3 5 8
3 6 4
4 6 6
6 5 1
0
the output would be:
0: 0 cost of 0
1: 0-1 cost of 2
2: 0-3-2 cost of 3
3: 0-3 cost of 1
4: 0-3-4 cost of 3
5: 0-3-6-5 cost of 6
6: 0-3-6 cost of 5

This article has been dead for over six months. Start a new discussion instead.