Created
November 18, 2020 12:59
-
-
Save Leovaldez42/209534f0c3faad0cef2169dc2d5ac575 to your computer and use it in GitHub Desktop.
The Dijkstra’s shortest path algorithm
This file contains 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 <limits.h> | |
#include <stdio.h> | |
#define V 6 | |
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 printSolution(int dist[]) | |
{ | |
printf("Vertex \t\t Distance from Source\n"); | |
for (int i = 0; i < V; i++) | |
printf("%d \t\t %d\n", i, dist[i]); | |
} | |
void dijkstra(int graph[V][V], int src) | |
{ | |
int dist[V]; | |
bool sptSet[V]; | |
for (int i = 0; i < V; i++) | |
dist[i] = INT_MAX, sptSet[i] = false; | |
dist[src] = 0; | |
for (int count = 0; count < V - 1; count++) { | |
int u = minDistance(dist, sptSet); | |
sptSet[u] = true; | |
for (int v = 0; v < V; 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]; | |
} | |
printSolution(dist); | |
} | |
int main() | |
{ | |
int graph[V][V] = { { 0, 2, 4, 0, 0, 0 }, | |
{ 2, 0, 1, 7, 0, 0 }, | |
{ 4, 1, 0, 0, 3, 0 }, | |
{ 0, 7, 0, 0, 2, 1 }, | |
{ 0 ,0, 3, 2, 0, 5 }, | |
{ 0, 0, 0, 1, 5, 0 } }; | |
dijkstra(graph, 0); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment