Dijkstra algorithm in c
On-campus and online computer science courses to Learn the basic concepts of Computer Science.This tutorial will cover c ,c++, java, data structure and algorithm,computer graphics,microprocessor,analysis of algorithms,Digital Logic Design and Analysis,computer architecture,computer networks,operating system.
code in C:# include<stdio.h> #define INFINITY 999 int cost[10][10],distance[10],p[10],visited[10],n,i,j,source,dest,current,path[10],min; void dijkstra(); int main() { printf("Enter the no.of vertices:"); scanf("%d",&n); printf("Enter the cost matrix:\n"); for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&cost[i][j]); printf("enter the source :"); scanf("%d",&source); printf("enter the destination:"); scanf("%d",&dest); dijkstra(); return 0; } void dijkstra() { //initialize output[],distance[] and visited[] for(i=0;i<n;i++) { distance[i]=INFINITY; visited[i]=0; } current = source; visited[current] = 1; distance[current] = 0; while(current != dest) { min=distance[current]; //check if a better path exists through current node for(i=0;i<n;i++) if(cost[current][i]!=0 && visited[i] != 1) if(cost[current][i]+min<distance[i]) { distance[i]=cost[current][i]+min; p[i]=current; } min=INFINITY; //To find node at minimum distance for(i=0;i<n;i++) if(visited[i]!=1 && distance[i]<min) { min=distance[i]; current=i; } visited[current]=1; } // to print Shortest path printf("\n Path=%d",dest); j=dest; do { j=p[j]; printf("<-%d",j); }while(j!=source); printf("\nShortest Distance = %d",distance[dest]); }output:-
Enter the no.of vertices:4 Enter the cost matrix: 0 5 6 0 5 0 6 0 6 6 0 8 0 0 8 0 enter the source :0 enter the destination:3 Path=3<-2<-0 Shortest Distance = 14 --------------------------------
0 comments: