# Dijkstra’s Shortest Path Algorithm | Greedy Algo | Factsprime

### Write a Modular C Programming code for ‎Dijkstra’s Shortest Path Algorithm DSA

Examples:

Input: src = 0, the graph is shown below.

Output: 0 4 12 19 21 11 9 8 14
Explanation: The distance from 0 to 1 = 4.
The minimum distance from 0 to 2 = 12. 0->1->2
The minimum distance from 0 to 3 = 19. 0->1->2->3
The minimum distance from 0 to 4 = 21. 0->7->6->5->4
The minimum distance from 0 to 5 = 11. 0->7->6->5
The minimum distance from 0 to 6 = 9. 0->7->6
The minimum distance from 0 to 7 = 8. 0->7
The minimum distance from 0 to 8 = 14. 0->1->2->8

CODE:

```#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include<stdbool.h>

#define V 9
#define INF INT_MAX

int minDistance(int dist[], bool sptSet[])
{
int min = INF, 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 dijkstra(int graph[V][V], int src)
{
int dist[V];
bool sptSet[V];

for (int i = 0; i < V; i++)
dist[i] = INF, 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] != INF
&& dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}

printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}

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;
}

```

OUTPUT

```Vertex          Distance from Source
0                  0
1                  4
2                  12
3                  19
4                  21
5                  11
6                  9
7                  8
8                  14```

Please find some more codes of Loops, Condition Statements, 1D Arrays, 2D Arrays, Strings, Pointers, Data Structures, Files, Linked lists, Stacks, Queues, Binary Trees, MISC, Solved model question papers & Hacker Rank all solutions on the below page:

Top 100+ C Programming codes – KLE Technological University

#### Welcome to FactsPrime

Sorry, We have detected that you have activated Ad-Blocker. Please Consider supporting us by disabling your Ad Blocker, It helps us in maintaining this website. To View the content, Please disable adblocker and refresh the page.

Thank You !!!