Dijkstra Algorithm On C

Dijkstra algorithm or used to be called as greedy algorithm is an algorithm that is usually used  for searching best path on several points. for example, suppose if there are 6 cities in a country (A, B, C, D, E, F), of course from one to the others will be separated by far distance. if i will go from city A to city D, i will need far distance. So, to get the shortest path, i need to do optimization using Dijkstra algorithm.As i know that this algorithm is the best one on optimization. Usually Dijkstra is represented by using graph with weight on each point to represent the distance, or cost to reach it.

to implement of it, here is the source code


#include <stdio.h>
#define inf 999
#define n 7
#define mem 1
#define nonm 0
int main(){
int weight[n][n]={0,2,4,20,12,5,3,
 2,0,2,5,7,40,9,
 4,2,0,3,6,5,40,
 20,5,3,0,6,10,32,
 12,7,6,6,0,1,20,
 5,40,5,10,1,0,10,
 3,9,40,32,20,10,0};

int s,t,pre[n];
int dist[n],perm[n];
int cur,i,k,dc,z;
int smal,newd;
char asal,tujuan;

printf("Simpul asal = ");scanf("%c",&asal);

switch (asal)
 {
 case 'a':
 s=0;
 break;
 case 'b':
 s=1;
 break;
 case 'c':
 s=2;
 break;
 case 'd':
 s=3;
 break;
 case 'e':
 s=4;
 break;
 case 'f':
 s=5;
 break;
 case 'g':
 s=6;
 break;
 default :
 printf("ERROR !!! \n");
 }

printf("Simpul tujuan = ");scanf("%c",&tujuan);scanf("%c",&tujuan);
 switch (tujuan)
 {
 case 'a':
 t=0;
 break;
 case 'b':
 t=1;
 break;
 case 'c':
 t=2;
 break;
 case 'd':
 t=3;
 break;
 case 'e':
 t=4;
 break;
 case 'f':
 t=5;
 break;
 case 'g':
 t=6;
 break;
 default :
 printf("ERROR !!! \n");
 }
 for (i=0;i<=6;i++){
 perm[i]=nonm;
 dist[i]=inf;
 }
perm[s]=mem;
dist[s]=0;
cur=s;
 while (cur!=t)
 {
 smal=inf;
 dc=dist[cur];
 for(i=0;i<=6;i++){
 if (perm[i] == nonm){
 newd=dc+weight[cur][i];
 if (newd<dist[i]){
 dist[i]=newd;
 pre[i]=cur;
 }
 if (dist[i]<smal){
 smal=dist[i];
 k=i;
 }
 }
 }
 cur=k;
 perm[cur]=mem;
 }
 printf("PATH = %i\n",dist[t]);
return (0);
}

Tagged:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: