Category Archives: Smart Algorithm

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);
}