I\'m trying to construct a weighted graph and use Dijkstra\'s algorithm to find
ID: 3911813 • Letter: I
Question
I'm trying to construct a weighted graph and use Dijkstra's algorithm to find the shortest path from node to node using an adjacency matrix. I need help coming up with algorithms for a priority queue and Djikstra's algorithm. This is the Graph.cpp file of the program. The main.cpp is separate. Attached are screenshots of what I have thus far. Any help would be greatly appreciated!
#include "Graph . hpp" 10 #include iostream> 11 using namespace std; 12 13 //Function to add a node 14 void Graph::add_node (int node) 15 16 17 18 19 20 this->node node visited new bool [node]; adjacencynew int* [node]; for (int rowe; row node 11 startExplanation / Answer
//implementing priority queue using array
struct priority_queue{
int vertex;
int weight;
};
struct priority_queue arr[20];
following 3 functions need to implement :
(1)insert():insertion will be done by adding item in array with complexity of O(1).
(2)get_highest_priority_element(): find by using linear search through array.
(3)delete_highest_priority_element():first using linear search find item then removing item by moving all
subsequent item one position back.
////dijkstra implementation
Following steps for implementing dijkstra using priority Queue.
1) At first,make an array equal to size of number of vertices in queue and initialize distances of all
vertices as INT_MAX.
2) Create an empty priority_queue p with every item as pair(weight, vertex).And each item are compared on basis
of their weight as priority.
3) now,put source vertex in p and initialize its weight as 0.
4) while p is not empty
a) Extract minimum distance vertex from p.
suppose it be u.
b) now,Loop through all adjacent of u and do
following for every vertex v.
If dist[v] > dist[u] + weight(u, v)
(i) Update distance of v
dist[v] = dist[u] + weight(u, v)
(ii) Insert v into the p
5) finally,print dist[] array.
void Graph::dijkstra(int source)
{
///here priority queue is implemented using stl library
priority_queue< iPair, vector <iPair> , greater<iPair> > p;
vector<int> dist(V, INF);
p.push(make_pair(0, source));
dist[source] = 0;
while (!p.empty())
{
int u = p.top().second;
p.pop();
list< pair<int, int> >::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
int v = (*i).first;
int weight = (*i).second;
if (dist[v] > dist[u] + weight)
{
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
// Print shortest distances stored in dist[]
cout<<"Vertex Distance from Source ";
for (int i = 0; i < V; ++i)
cout<< i<<" "<<dist[i]<<" ";
}