Scribd
Upload
35 views5 pages

Source Code For Dijkstra Program

This document contains the source code for implementing Dijkstra's algorithm to find the shortest paths between vertices in a graph. It includes function definitions for initializing the graph, finding the nearest unvisited vertex, running Dijkstra's algorithm from a source vertex, and displaying the output. The code takes the number of vertices and edge costs as input, runs Dijkstra's algorithm, and outputs the shortest distance from the source to each vertex.

Uploaded by

Anonymous G0hDK6cyc
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
35 views5 pages

Source Code For Dijkstra Program

This document contains the source code for implementing Dijkstra's algorithm to find the shortest paths between vertices in a graph. It includes function definitions for initializing the graph, finding the nearest unvisited vertex, running Dijkstra's algorithm from a source vertex, and displaying the output. The code takes the number of vertices and edge costs as input, runs Dijkstra's algorithm, and outputs the shortest distance from the source to each vertex.

Uploaded by

Anonymous G0hDK6cyc
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

SOURCE CODE FOR DIJKSTRA PROGRAM:

#include<stdio.h>

//DECLARATION OF HEADER FILES

#define INFINITY 9999

//Initialize INFINITY value

int n,cost[10][10],dist[10],visit[10],front,rear,v;//Declaration of needed Variables


void Initial(int n)// Function Definition
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cost[i][j] = INFINITY; //Initialize all edge values as infinity
}
}

for(i=1;i<=n;i++)
{
dist[i] = INFINITY;//Initialize Assign Infinity for all distance
visit[i] = 0;

//Assigning not yet visited any nodes

}
}
int nearest()//Function Definition
{
int i,node, weight;
weight = INFINITY;
for(i=1;i<=n;i++)
{
if(visit[i] == 0 && dist[i] < weight) //Checking for not yet visited
node and distance less than infinity

{
weight = dist[i];
node=i;
}
}
return node;
}
void Dijkstra(int v)//Function Definition
{
int i,u,q,alt;//Initialize needed variables
dist[v]=0;

for(i=1;i<=n;i++)
{
u=nearest();//Function Call
for(v=1;v<=n;v++)
{
if(cost[u][v] == INFINITY)
continue;
alt = dist[u] + cost[u][v];//Update the distance value
if(alt < dist[v])
{
dist[v] = alt;
}
}
visit[u] = 1;//node visited
}
}

void display()//Function Definition


{
int i,j;
printf("\nCOST MATRIX\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t", cost[i][j]);//Display the cost values

}
printf("\n");
}
}
int main()
{
int i,j,k,m;//Declaration of needed variables
printf("\n\t\t\t\tDIJKSTRA PROGRAM");
printf("\nENTER THE NUMBER OF VERTICES...");
scanf("%d",&n);//Getting n number of values
Initial(n);//Function Call
printf("\nNOTE...IF EDGE DOES NOT EXIST ENTER 9999\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("ENTER THE DISTANCE BETWEEN %d AND %d....",i,j);
scanf("%d" ,&cost[i][j]);//Getting the distance value

}
}
display();//Function Call
printf("\nENTER THE SOURCE VERTEX...");
scanf("%d",&v);//Getting the source vertex
Dijkstra(v);//Function Call
printf("\nRESULT...");
for(i=1;i<=n;i++)
{
printf("\nDISTANCE OF %d IS...",i);
printf("%d",dist[i]);//Print the Distance value
printf("\n");
}
return 0;
}

OUTPUT:

You might also like