Scribd
Upload
9 views4 pages

Exp 7 DAA 33

This document contains a C program implementing Dijkstra's algorithm to find the shortest paths from a starting node to all other nodes in a graph represented by an adjacency matrix. It prompts the user to input the number of vertices and the adjacency matrix, then calculates and displays the shortest distances and paths. The program utilizes arrays to store costs, distances, predecessors, and visited nodes during the algorithm's execution.

Uploaded by

vitthalkolapkar16
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
9 views4 pages

Exp 7 DAA 33

This document contains a C program implementing Dijkstra's algorithm to find the shortest paths from a starting node to all other nodes in a graph represented by an adjacency matrix. It prompts the user to input the number of vertices and the adjacency matrix, then calculates and displays the shortest distances and paths. The program utilizes arrays to store costs, distances, predecessors, and visited nodes during the algorithm's execution.

Uploaded by

vitthalkolapkar16
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
You are on page 1/ 4

EXPERIMENT No.

#include<stdio.h>

#include<conio.h>

#define INFINITY 9999

#define MAX 10

void dijkstra(int G[MAX][MAX],int n,int startnote);

int main()

int G[MAX][MAX],i,j,n,u;

printf("Enter number of vertics:");

scanf("%d",&n);

printf("\n Enter the adjaceny matrix:\n");

for(i=0;i<n;i++)

for(j=0;j<n;j++)

scanf("%d",&G[i][j]);

printf("\n Enter the starting node:");

scanf("%d",&u);

dijkstra(G,n,u);

return 0;

void dijkstra(int G[MAX][MAX],int n,int startnode)

int cost[MAX][MX],distance[MAX],pred[MAX];
EXPERIMENT No.7

int visited[MAX],count,mindistance,nextnode,i,j;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(G[i][j]==0)

cost[i][j]=INFINITY;

else

cost[i][j]=G[i][j];

for(i=0;i<n;i++)

distance[i]=cost[startnode][i];

pred[i]=startnode;

visited[i]=0;

distance[startnode]=0;

visited[startnode]=1;

count=1;

while(count<n-1)

mindistance=INFINITY;

for(i=0;i<n;i++)

if(distance[i]<mindistance&&!visited[i])

{
EXPERIMENT No.7

mindistance=distance[i];

nextnode=i;

visited[nextnode]=1;

for(i=0;i<n;i++)

if(!visited[i])

if(mindistance+cost[nextnode][i]<distance[i])

distance[i]=mindistance+cost[nextnode][i];

pred[i]=nextnode;

count++;

for(i=0;i<n;i++)

if(i!=startnode)

printf("\n Distanceof node%d=%d",distance[i]);

printf("\n Path=%d",i);

j=i;

do

j=pred[j];
EXPERIMENT No.7

printf("<=%d",j);

while(j!=startnode);

You might also like