Created
August 6, 2019 08:07
-
-
Save ajinkyajawale14499/4155eadb45adc856e29d661c05194d4f to your computer and use it in GitHub Desktop.
Dijkstra Shortest path algorithm using greedy method
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
#include<bits/stdc++.h> | |
#define V 10 | |
#define INT_MAX 99999999 | |
using namespace std; | |
int mindistance(int dist[],bool sptset[]) | |
{ | |
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; | |
} | |
void printdijkstra(int dist[V],int n) | |
{ | |
for(int i=0;i<n;i++) | |
printf("%d tt %d \n",i,dist[i] ); | |
} | |
void 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 be 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 | |
printdijkstra(dist, V); | |
} | |
} | |
int main() | |
{ | |
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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment