[Algorithm][Greedy]Dijsktra Algorithm

// A C++ program for Dijkstra‘s single source shortest path algorithm.// The program is for adjacency matrix representation of the graph ?#include <stdio.h>#include <limits.h> ?// Number of vertices in the graph#define V 9 ?// A utility function to find the vertex with minimum distance value, from// the set of vertices not yet included in shortest path treeint minDistance(int dist[], bool sptSet[]){ ??// Initialize min value ??int min = INT_MAX, min_index; ????for (int v = 0; v < V; v++) ????if (sptSet[v] == false && dist[v] <= min) ????????min = dist[v], min_index = v; ????return min_index;} ?// A utility function to print the constructed distance arrayint printSolution(int dist[], int n){ ??printf("Vertex ??Distance from Source\n"); ??for (int i = 0; i < V; i++) ?????printf("%d tt %d\n", i, dist[i]);} ?// Function that implements Dijkstra‘s single source shortest path algorithm// for a graph represented using adjacency matrix representationvoid dijkstra(int graph[V][V], int src){ ????int dist[V]; ????// The output array. ?dist[i] will hold the shortest ?????????????????????// distance from src to i ??????bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest ????????????????????// path tree or shortest distance from src to i is finalized ??????// Initialize all distances as INFINITE and stpSet[] as false ????for (int i = 0; i < V; i++) ???????dist[i] = INT_MAX, sptSet[i] = false; ??????// Distance of source vertex from itself is always 0 ????dist[src] = 0; ??????// Find shortest path for all vertices ????for (int count = 0; count < V-1; count++) ????{ ??????// Pick the minimum distance vertex from the set of vertices not ??????// yet processed. u is always equal to src in the first iteration. ??????int u = minDistance(dist, sptSet); ????????// Mark the picked vertex as processed ??????sptSet[u] = true; ????????// Update dist value of the adjacent vertices of the picked vertex. ??????for (int v = 0; v < V; v++) ??????????// Update dist[v] only if is not in sptSet, there is an edge from ?????????// u to v, and total weight of path from src to ?v through u is ?????????// smaller than current value of dist[v] ????????if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX ???????????????????????????????????????&& dist[u]+graph[u][v] < dist[v]) ???????????dist[v] = dist[u] + graph[u][v]; ????} ??????// print the constructed distance array ????printSolution(dist, V);} ?// driver program to test above functionint main(){ ??/* Let us create the example graph discussed above */ ??int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0}, ?????????????????????{4, 0, 8, 0, 0, 0, 0, 11, 0}, ?????????????????????{0, 8, 0, 7, 0, 4, 0, 0, 2}, ?????????????????????{0, 0, 7, 0, 9, 14, 0, 0, 0}, ?????????????????????{0, 0, 0, 9, 0, 10, 0, 0, 0}, ?????????????????????{0, 0, 4, 14, 10, 0, 2, 0, 0}, ?????????????????????{0, 0, 0, 0, 0, 2, 0, 1, 6}, ?????????????????????{8, 11, 0, 0, 0, 0, 1, 0, 7}, ?????????????????????{0, 0, 2, 0, 0, 0, 6, 7, 0} ????????????????????}; ?????dijkstra(graph, 0); ?????return 0;}

// C / C++ program for Dijkstra‘s shortest path algorithm for adjacency// list representation of graph #include <stdio.h>#include <stdlib.h>#include <limits.h> // A structure to represent a node in adjacency liststruct AdjListNode{ ???int dest; ???int weight; ???struct AdjListNode* next;}; // A structure to represent an adjacency liatstruct 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 nodestruct 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 verticesstruct Graph* createGraph(int V){ ???struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph)); ???graph->V = V; ????// Create an array of adjacency lists. ?Size of array will be V ???graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList)); ?????// Initialize each adjacency list as empty by making head as NULL ???for (int i = 0; i < V; ++i) ???????graph->array[i].head = NULL; ????return graph;} // Adds an edge to an undirected graphvoid 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; ????// Since graph is undirected, add an edge from dest to src also ???newNode = newAdjListNode(src, weight); ???newNode->next = graph->array[dest].head; ???graph->array[dest].head = newNode;} // Structure to represent a min heap nodestruct MinHeapNode{ ???int ?v; ???int dist;}; // Structure to represent a min heapstruct 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 Nodestruct 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 Heapstruct 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 heapifyvoid 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 < minHeap->size && ???????minHeap->array[left]->dist < minHeap->array[smallest]->dist ) ?????smallest = left; ????if (right < minHeap->size && ???????minHeap->array[right]->dist < minHeap->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 notint isEmpty(struct MinHeap* minHeap){ ???return minHeap->size == 0;} // Standard function to extract minimum node from heapstruct 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 heapvoid 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 < minHeap->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 notbool isInMinHeap(struct MinHeap *minHeap, int v){ ??if (minHeap->pos[v] < minHeap->size) ????return true; ??return false;} // A utility function used to print the solutionvoid printArr(int dist[], int n){ ???printf("Vertex ??Distance from Source\n"); ???for (int i = 0; i < n; ++i) ???????printf("%d \t\t %d\n", i, dist[i]);} // The main function that calulates distances of shortest paths from src to all// vertices. It is a O(ELogV) functionvoid dijkstra(struct Graph* graph, int src){ ???int V = graph->V;// Get the number of vertices in graph ???int dist[V]; ?????// dist values used to pick minimum weight edge in cut ????// 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 < V; ++v) ???{ ???????dist[v] = INT_MAX; ???????minHeap->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] < dist[v]) ???????????{ ???????????????dist[v] = dist[u] + pCrawl->weight; ????????????????// update distance value in min heap also ???????????????decreaseKey(minHeap, v, dist[v]); ???????????} ???????????pCrawl = pCrawl->next; ???????} ???} ????// print the calculated shortest distances ???printArr(dist, V);} ?// Driver program to test above functionsint main(){ ???// create the graph given in above fugure ???int V = 9; ???struct Graph* graph = createGraph(V); ???addEdge(graph, 0, 1, 4); ???addEdge(graph, 0, 7, 8); ???addEdge(graph, 1, 2, 8); ???addEdge(graph, 1, 7, 11); ???addEdge(graph, 2, 3, 7); ???addEdge(graph, 2, 8, 2); ???addEdge(graph, 2, 5, 4); ???addEdge(graph, 3, 4, 9); ???addEdge(graph, 3, 5, 14); ???addEdge(graph, 4, 5, 10); ???addEdge(graph, 5, 6, 2); ???addEdge(graph, 6, 7, 1); ???addEdge(graph, 6, 8, 6); ???addEdge(graph, 7, 8, 7); ????dijkstra(graph, 0); ????return 0;}