I need to make a weighted graph and use Dijkstra\'s algorithm to calculate the s
ID: 3914857 • Letter: I
Question
I need to make a weighted graph and use Dijkstra's algorithm to calculate the shortest path from a start node to other nodes in the graph. The following is code in my constructor file so far. I need to add an edge, remove an edge, add a node, remove a node, implement a priority queue, and implement Dijkstra's algorithm. Any improvements I can make to my code? Not exactly sure how to go about Dijkstra's algorithm and making a priority queue. Any help would be greatly appreciated!
9 #includ@"Graph.hpp" 10 #include node-node; visitednew bool [node] adjacencynew ints [node] 18 19 20 for (int row 0; row node end> node I 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 (Even if v is
already there)
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]<<" ";}