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