Scribd
Upload
8 views3 pages

Dijkstra's Algorithm Implementation in C

The document presents a C program implementing Dijkstra's algorithm for finding the single-source shortest path in a graph. It defines functions to calculate minimum distances and to perform the greedy algorithm, displaying the shortest distances from the source vertex to all other vertices. The program initializes a graph and outputs the shortest distances from the source vertex A.

Uploaded by

kesavat0001
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
8 views3 pages

Dijkstra's Algorithm Implementation in C

The document presents a C program implementing Dijkstra's algorithm for finding the single-source shortest path in a graph. It defines functions to calculate minimum distances and to perform the greedy algorithm, displaying the shortest distances from the source vertex to all other vertices. The program initializes a graph and outputs the shortest distances from the source vertex A.

Uploaded by

kesavat0001
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

single-source shortest path algorithm program

#include<stdio.h>

#include<limits.h>

#include<stdbool.h>

int min_dist(int[], bool[]);

void greedy_dijsktra(int[][6],int);

int min_dist(int dist[], bool visited[]){ // finding minimum dist

int minimum=INT_MAX,ind;

for(int k=0; k<6; k++) {

if(visited[k]==false && dist[k]<=minimum) {

minimum=dist[k];

ind=k;

return ind;

void greedy_dijsktra(int graph[6][6],int src){

int dist[6];

bool visited[6];

for(int k = 0; k<6; k++) {

dist[k] = INT_MAX;

visited[k] = false;

}
dist[src] = 0; // Source vertex dist is set 0

for(int k = 0; k<6; k++) {

int m=min_dist(dist,visited);

visited[m]=true;

for(int k = 0; k<6; k++) {

// updating the dist of neighbouring vertex

if(!visited[k] && graph[m][k] && dist[m]!=INT_MAX && dist[m]


+graph[m][k]<dist[k])

dist[k]=dist[m]+graph[m][k];

printf("Vertex\t\tdist from source vertex\n");

for(int k = 0; k<6; k++) {

char str=65+k;

printf("%c\t\t\t%d\n", str, dist[k]);

int main(){

int graph[6][6]= {

{0, 1, 2, 0, 0, 0},

{1, 0, 0, 5, 1, 0},

{2, 0, 0, 2, 3, 0},

{0, 5, 2, 0, 2, 2},
{0, 1, 3, 2, 0, 1},

{0, 0, 0, 2, 1, 0}

};

greedy_dijsktra(graph,0);

return 0;

Output
Vertex dist from source vertex
A 0
B 1
C 2
D 4
E 2
F 3

You might also like