Question: please fix these two functions syntax and any other issues #include using namespace std; / / ? ? ? ? ? ? ? ? include

please fix these two functions syntax and any other issues
#include
using namespace std;
//???????? include your min heap class. It will be used in Dijkstra's algorithm
#include "minHeap.h"
//???????? include your graph class. You will pass a graph to Dijkstra's algorithm
#include "graph.h"
//Each vertex has a vertex number, current shortest distance and predecessor
struct vertex
{
int vertexNum; //the vertex number
int curDist; //the current shortest distance from start to the vertex
int predecessor; //the predecessor along the shortest path to the vertex
};
int* locator; ///tells where each vertex exists within the heap. The dynamic array pointed to by this pointer will be created inside dijkstraSHortestPath() down below
//e.g. vertex numbers in heap[3,1,2,4,0] vertex 3 is at the root because its curDist is the smallest
// locator should look like this [4,1,2,0,3] vertex 3 can be found at 0. vertex 0 can be found at 4 in heap
//This is a global variable (sounds terrible), but that is ok for this application. The reason why it is declared global is that it is accessed from mySwap() down below. mySwap() is called from the min heap class. We are not passing locator to the min heap class.
//this will be called from the min heap class. Each element in the heap is a vertex which consists of vertexNum, curDist and predecesso
//This function will show the path from stat to destination
//MH is the mean heap which contains the vertexNum, curDist and precessor of all the vertices created by Dijkstra's algorithm
//start is the start vertex. Dijkstra's algorithm calculated the shortest distance from start to every other vertex
//This function shows the shortest path from start to destination in the following format.
// The shortest path from 3 to 5 is 3045
// The distance is 8
void showShortestDistance(const minHeap& MH, int start)
{
stack pathStack;
int current = dest;
while(current != start){
pathStack.push(current);
current = vertex[current].predecessor; // Assuming MH is a structure with a member named 'predecessor'
}
pathStack.push(start); // Push the start vertex
cout << "The shortest path from "<< start <<" to "<< dest <<" is: ";
while(!pathStack.empty()){
cout << pathStack.top()<<"";
pathStack.pop();
}
cout <<"
The distance is "<< vertex[dest].curDist << endl;
}
//Dijkstra's shortest path algorithm - generating a table that contains the shortest distance from start to every other vertex and the predecessor of each vertex.
//g is a graph. We will pass the graph created in our client file.
//start is the start vertex.
void DijkstraShortestPath(const graph& g, int start)
{
minHeap minHeap(g.getNumVerticses(); //Create a min heap of the data type, vertex.
std::vector* locator = new std::vector(g.getNumVertices()); //Create a dynamic array pointed to by locator, which is declared globally above.
//locator is an array containing the location of each vertex in the heap
//locator[0] always tells the location/index of vertex 0 in the heap. If the locator looks like [3,0,1,2], vertex 0 is located at index 3 in the heap, veertex 1 is located at index 0(meaning vertex 1 has the minimum distance).
//The following for loop populates the min heap with all the vertices. Set curDist to 999 and predecessor to -1.
//e.g. vertex for vertext number 0 should like this [0,999,-1]
// vertex for vertext number 1 should like this [1,999,-1]
// Populate the min heap with all vertices
vertex ver;
for (int i =0; i < g.getNumVertices(); i++){
ver.vertexNum = i;
ver.curDist =999; // Initialize with a large distance
ver.predecessor =-1;
minHeap.insert(ver);
}
// Initialize locator array
for (int i =0; i < g.getNumVertices(); i++){
(*locator)[i]= i;
}
// Update start vertex
ver.vertexNum = start;
ver.curDist =0;
ver.predecessor =-1;
minHeap.updateElem((*locator)[start], ver); // Update and fix heap
// Dijkstra's Algorithm
while (!minHeap.isEmpty()){
vertex u = minHeap.extractMin();
int uIndex =(*locator)[u.vertexNum]; // Get index in locator
// For each neighbor v of u
for (auto& edge : g.getNeighbors(u.vertexNum)){
int v = edge.first;
int weight = edge.second;
int vIndex =(*locator)[v]; // Get index of v in locator
// Relaxation
if (minHeap.contains(vIndex) && u.curDist + weight < minHeap.getElem(vIndex).curDist){
ver.vertexNum = v;
ver.curDist = u.curDist + weight;
ver.predecessor = u.vertexNum;
minHeap.updateElem(vIndex, ver); // Update and fix heap
}
}
}
showShortestDistance(g, start); // Show results (assuming you have this function)
delete locator; // Free memory
}
}

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!