Question
********************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************** Every things work good except of Q part (Shortest path path ,it does not print the heap), also for P and Q when it's
**********************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************
Every things work good except of Q part (Shortest path path ,it does not print the heap), also for P and Q when it's P 1 0 or Q 1 0 it does not print index out of bound, also there should be 8 files, so the code should be seprate in main.cpp, main.h , heap.cpp, heap.h , graph.cpp , graph.h , util.cpp , util.h
main.h file
#ifndef GRAPH_H #define GRAPH_H
#include
// A structure to represent a node in adjacency list struct AdjListNode { int dest; int weight; struct AdjListNode* next; };
// A structure to represent an adjacency liat struct AdjList { struct AdjListNode *head; // pointer to head node of list };
// A structure to represent a graph. A graph is an array of adjacency lists. // Size of array will be V (number of vertices in graph) struct Graph { int V; struct AdjList* array; };
// A utility function to create a new adjacency list node struct AdjListNode* newAdjListNode(int dest, int weight) { struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode)); newNode->dest = dest; newNode->weight = weight; newNode->next = NULL; return newNode; }
// A utility function that creates a graph of V vertices struct Graph* createGraph(int V) { struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph)); graph->V = V+1; // Create an array of adjacency lists. Size of array will be V graph->array = (struct AdjList*) malloc((V+1) * sizeof(struct AdjList)); // Initialize each adjacency list as empty by making head as NULL for (int i = 0; i array[i].head = NULL; return graph; }
// Adds an edge to an directed graph void addEdge(struct Graph* graph, int src, int dest, int weight) { // Add an edge from src to dest. A new node is added to the adjacency // list of src. The node is added at the begining struct AdjListNode* newNode = newAdjListNode(dest, weight); newNode->next = graph->array[src].head; graph->array[src].head = newNode; }
// Structure to represent a min heap node struct MinHeapNode { int v; int dist; };
// Structure to represent a min heap struct MinHeap { int size; // Number of heap nodes present currently int capacity; // Capacity of min heap int *pos; // This is needed for decreaseKey() struct MinHeapNode **array; };
// A utility function to create a new Min Heap Node struct MinHeapNode* newMinHeapNode(int v, int dist) { struct MinHeapNode* minHeapNode = (struct MinHeapNode*) malloc(sizeof(struct MinHeapNode)); minHeapNode->v = v; minHeapNode->dist = dist; return minHeapNode; }
// A utility function to create a Min Heap struct MinHeap* createMinHeap(int capacity) { struct MinHeap* minHeap = (struct MinHeap*) malloc(sizeof(struct MinHeap)); minHeap->pos = (int *)malloc(capacity * sizeof(int)); minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHeapNode**) malloc(capacity * sizeof(struct MinHeapNode*)); return minHeap; }
// A utility function to swap two nodes of min heap. Needed for min heapify void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) { struct MinHeapNode* t = *a; *a = *b; *b = t; }
// A standard function to heapify at given idx // This function also updates position of nodes when they are swapped. // Position is needed for decreaseKey() void minHeapify(struct MinHeap* minHeap, int idx) { int smallest, left, right; smallest = idx; left = 2 * idx + 1; right = 2 * idx + 2; if (left size && minHeap->array[left]->dist array[smallest]->dist ) smallest = left; if (right size && minHeap->array[right]->dist array[smallest]->dist ) smallest = right; if (smallest != idx) { // The nodes to be swapped in min heap MinHeapNode *smallestNode = minHeap->array[smallest]; MinHeapNode *idxNode = minHeap->array[idx]; // Swap positions minHeap->pos[smallestNode->v] = idx; minHeap->pos[idxNode->v] = smallest; // Swap nodes swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } }
// A utility function to check if the given minHeap is ampty or not int isEmpty(struct MinHeap* minHeap) { return minHeap->size == 0; }
// Standard function to extract minimum node from heap struct MinHeapNode* extractMin(struct MinHeap* minHeap) { if (isEmpty(minHeap)) return NULL; // Store the root node struct MinHeapNode* root = minHeap->array[0]; // Replace root node with last node struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1]; minHeap->array[0] = lastNode; // Update position of last node minHeap->pos[root->v] = minHeap->size-1; minHeap->pos[lastNode->v] = 0; // Reduce heap size and heapify root --minHeap->size; minHeapify(minHeap, 0); return root; }
// Function to decreasy dist value of a given vertex v. This function // uses pos[] of min heap to get the current index of node in min heap void decreaseKey(struct MinHeap* minHeap, int v, int dist) { // Get the index of v in heap array int i = minHeap->pos[v]; // Get the node and update its dist value minHeap->array[i]->dist = dist; // Travel up while the complete tree is not hepified. // This is a O(Logn) loop while (i && minHeap->array[i]->dist array[(i - 1) / 2]->dist) { // Swap this node with its parent minHeap->pos[minHeap->array[i]->v] = (i-1)/2; minHeap->pos[minHeap->array[(i-1)/2]->v] = i; swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]); // move to parent index i = (i - 1) / 2; } }
// A utility function to check if a given vertex // 'v' is in min heap or not bool isInMinHeap(struct MinHeap *minHeap, int v) { if (minHeap->pos[v] size) return true; return false; }
void printPath(int parent[], int j) { // Base Case : If j is source if (parent[j]==-1) return; printPath(parent, parent[j]); printf("%d ", j); }
// The main function that calulates distances of shortest paths from src to all // vertices. It is a O(ELogV) function void dijkstra(struct Graph* graph, int src,int dest) { int V = graph->V;// Get the number of vertices in graph int dist[V]; // dist values used to pick minimum weight edge in cut int parent[V]; //printing path // minHeap represents set E struct MinHeap* minHeap = createMinHeap(V); // Initialize min heap with all vertices. dist value of all vertices for (int v = 0; v array[v] = newMinHeapNode(v, dist[v]); minHeap->pos[v] = v; } // Make dist value of src vertex as 0 so that it is extracted first minHeap->array[src] = newMinHeapNode(src, dist[src]); minHeap->pos[src] = src; dist[src] = 0; decreaseKey(minHeap, src, dist[src]); // Initially size of min heap is equal to V minHeap->size = V; // In the followin loop, min heap contains all nodes // whose shortest distance is not yet finalized. while (!isEmpty(minHeap)) { // Extract the vertex with minimum distance value struct MinHeapNode* minHeapNode = extractMin(minHeap); int u = minHeapNode->v; // Store the extracted vertex number // Traverse through all adjacent vertices of u (the extracted // vertex) and update their distance values struct AdjListNode* pCrawl = graph->array[u].head; while (pCrawl != NULL) { int v = pCrawl->dest; // If shortest distance to v is not finalized yet, and distance to v // through u is less than its previously calculated distance if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX && pCrawl->weight + dist[u] weight; // update distance value in min heap also decreaseKey(minHeap, v, dist[v]); } pCrawl = pCrawl->next; } } // print the calculated shortest distances cout
void printGraph(struct Graph* graph) { int v; for (v =1 ; v #endif main.cpp #include int main (int argc,char **argv) { string line,cmd; string c[3]; char choice; int so,d; vector GRAPHinput3.txt 16 31 1 3 8 9 10 5 4 8 1 14 1 1 13 5 9 10 8 1 7 16 5 3 9 4 9 5 6 11 3 6 16 4 18 1 14 3 6 2 7 13 11 5 8 10 1 10 13 7 7 4 2 3 5 11 5 6 8 11 16 8 15 1 1 12 15 1 11 6 12 2 7 5 1 13 11 8 12 1 3 13 2 1 16 23 2 5 3 6 5 1 10 2 17 OUTPUT compiling: g++ -std=c++11 main.cpp run : ./a.out ********************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************** Every things work good except of Q part (Shortest path path ,it does not print the heap), also for P and Q when it's P 1 0 or Q 1 0 it does not print index out of bound, also there should be 8 files, so the code should be seprate in main.cpp, main.h , heap.cpp, heap.h , graph.cpp , graph.h , util.cpp , util.h
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started