[C++]Using a min-heap and priority queue, write Dijkstra’s Shortest Path Algorit

Question

[C++]Using a min-heap and priority queue, write Dijkstra’s Shortest Path Algorithm on the Adjacency Matrix using the source and target vertex.

Adjacency Matrix:

0 8 2 5 0 0 0 0
8 0 0 2 0 13 0 0
2 0 0 2 5 0 0 0
5 2 2 0 1 6 3 0
0 0 5 1 0 0 1 0
0 13 0 6 0 0 2 3
0 0 0 3 1 2 0 6
0 0 0 0 0 3 6 0

Input/Output Format:
Please enter location of graph file to load: graph_1_win.txt
Please enter the index of the starting vertex: 0
Please enter the index of the target vertex: 7
The shortest path from vertex 0 to vertex 7 is:
0 to 2: 2
2 to 3: 2
3 to 4: 1
4 to 6: 1
6 to 5: 2
5 to 7: 3
Total path length is 11

Explanation / Answer

#include <cstdio>
#include <climits>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;

/*
* Indexed min priority queue
* Supports insertion in O(log N), deletion of any key (regardless of whether
* the key is the minimum key or not) in O(log N) and changes to key values
* in O(log N), where N is the number of
* elements currently in the PQ
*/
class MinIndexedPQ {
int NMAX, N, *heap, *index, *keys;

void swap(int i, int j) {
int t = heap[i]; heap[i] = heap[j]; heap[j] = t;
index[heap[i]] = i; index[heap[j]] = j;
}
void bubbleUp(int k) {
while(k > 1 && keys[heap[k/2]] > keys[heap[k]]) {
swap(k, k/2);
k = k/2;
}
}
void bubbleDown(int k) {
int j;
while(2*k <= N) {
j = 2*k;
if(j < N && keys[heap[j]] > keys[heap[j+1]])
j++;
if(keys[heap[k]] <= keys[heap[j]])
break;
swap(k, j);
k = j;
}
}
public:
// Create an empty MinIndexedPQ which can contain atmost NMAX elements
MinIndexedPQ(int NMAX) {
this->NMAX = NMAX;
N = 0;
keys = new int[NMAX + 1];
heap = new int[NMAX + 1];
index = new int[NMAX + 1];
for(int i = 0; i <= NMAX; i++)
index[i] = -1;
}
~MinIndexedPQ() {
delete [] keys;
delete [] heap;
delete [] index;
}
// check if the PQ is empty
bool isEmpty() {
return N == 0;
}
// check if i is an index on the PQ
bool contains(int i) {
return index[i] != -1;
}
// associate key with index i; 0 < i < NMAX
void insert(int i, int key) {
N++;
index[i] = N;
heap[N] = i;
keys[i] = key;
bubbleUp(N);
}
// delete the minimal key and return its associated index
// Warning: Don't try to read from this index after calling this function
int deleteMin() {
int min = heap[1];
swap(1, N--);
bubbleDown(1);
index[min] = -1;
heap[N+1] = -1;
return min;
}
// decrease the key associated with index i to the specified value
void decreaseKey(int i, int key) {
keys[i] = key;
bubbleUp(index[i]);
}
};

// representation of directed edge to vertex 'to' having weight 'weight'
struct Edge {
int to, weight;
};

typedef vector <Edge> adjList;

int main() {
int V, E, i, N, u, v, cost, *dist, *edgeTo, s;
adjList *G;
stack <int> path;

  
scanf("%d %d", &V, &E); // Enter the number of vertices and edges
G = new adjList[V];
for(i=0; i<E; i++) { // Enter E directed edges u -> v having weight 'cost'
scanf("%d %d %d", &u, &v, &cost);
G[u].push_back((Edge){v, cost}); // add edge to adjacency list of u
}
scanf("%d", &s); // Enter the source vertex

dist = new int[V];
for(i=0; i<V; i++)
dist[i] = INT_MAX;
dist[s] = 0;
edgeTo = new int[V];
edgeTo[s] = s;

MinIndexedPQ pq(V);
pq.insert(s, 0);

while(!pq.isEmpty()) {
u = pq.deleteMin();
for(adjList::iterator it = G[u].begin(); it != G[u].end(); it++) {
v = it->to;
cost = dist[u] + it->weight;
if(cost < dist[v]) {
dist[v] = cost;
edgeTo[v] = u;
if(pq.contains(v)) pq.decreaseKey(v, cost);
else pq.insert(v, cost);
}
}
}

while(true) {
scanf("%d", &v); // Enter the target vertex v
if(v < 0) break;

u = v;
while(edgeTo[u] != u) {
path.push(edgeTo[u]);
u = edgeTo[u];
}
while(!path.empty()) { // print path from s to v
printf("%d-", path.top());
path.pop();
}
printf("%d ", v);
printf("%d ", dist[v]); // print cost of shortest path from s to v
}

delete [] dist;
delete [] edgeTo;
delete [] G;

return 0;
}

**NOTE: Due to lack of time, I could not implement the logic to read the graph details from the file. Please create one more post for this and I will answer it. Sorry for the incovenience caused.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.