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
eg vertex numbers in heap vertex is at the root because its curDist is the smallest
locator should look like this vertex can be found at vertex can be found at 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 to is
The distance is
void showShortestDistanceconst minHeap& MH int start
stack pathStack;
int current dest;
whilecurrent start
pathStack.pushcurrent;
current vertexcurrentpredecessor; Assuming MH is a structure with a member named 'predecessor'
pathStack.pushstart; Push the start vertex
cout "The shortest path from start to dest is: ;
whilepathStack.empty
cout pathStack.top;
pathStack.pop;
cout
The distance is vertexdestcurDist endl;
Dijkstras 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 DijkstraShortestPathconst graph& g int start
minHeap minHeapggetNumVerticses; Create a min heap of the data type, vertex.
std::vector locator new std::vectorggetNumVertices; 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 always tells the locationindex of vertex in the heap. If the locator looks like vertex is located at index in the heap, veertex is located at index meaning vertex has the minimum distance
The following for loop populates the min heap with all the vertices. Set curDist to and predecessor to
eg vertex for vertext number should like this
vertex for vertext number should like this
Populate the min heap with all vertices
vertex ver;
for int i ; i ggetNumVertices; i
ver.vertexNum i;
ver.curDist ; Initialize with a large distance
ver.predecessor ;
minHeap.insertver;
Initialize locator array
for int i ; i ggetNumVertices; i
locatori i;
Update start vertex
ver.vertexNum start;
ver.curDist ;
ver.predecessor ;
minHeap.updateElemlocatorstart ver; Update and fix heap
Dijkstra's Algorithm
while minHeap.isEmpty
vertex u minHeap.extractMin;
int uIndex locatoruvertexNum; Get index in locator
For each neighbor v of u
for auto& edge : ggetNeighborsuvertexNum
int v edge.first;
int weight edge.second;
int vIndex locatorv; Get index of v in locator
Relaxation
if minHeapcontainsvIndex && ucurDist weight minHeap.getElemvIndexcurDist
ver.vertexNum v;
ver.curDist ucurDist weight;
ver.predecessor uvertexNum;
minHeap.updateElemvIndex ver; Update and fix heap
showShortestDistanceg 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
Question Has Been Solved by an Expert!
Get step-by-step solutions from verified subject matter experts
Step: 2 Unlock
Step: 3 Unlock
