Skip to main content

Finding Shortest Path From Source to Destination using dijkstra algorithm usinc C program.

#include<stdio.h>
#include<conio.h>
#define IN 9999
#define MAX 10

void dj(int G[MAX][MAX],int n,int startnode,int dst);
void main()
{
int j,i,node,con[10][10],s,d;
clrscr();
printf("Enter No of Nodes::");
scanf("%d",&node);
for(i=0;i<node;i++)
{
for(j=0;j<node;j++)
{

printf("Node %d is conneted with node %d::",i,j);
a:
scanf("%d",&con[i][j]);
if(con[i][j]!=0 && con[i][j]!=1)
{
goto a;
}
}
}
printf("MATRIX:");
for(i=0;i<node;i++)
{
printf("\n");
for(j=0;j<node;j++)
{
printf("%d ",con[i][j]);
}
}

printf("\nENTER SOURCE & DESTINATION::");
scanf("%d%d",&s,&d);
dj(con,node,s,d);

}














void dj(int G[MAX][MAX],int n,int startnode,int dst)
{

    int cost[MAX][MAX],distance[MAX],pred[MAX];
    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]=IN;
    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=IN;

for(i=0;i<n;i++)
    if(distance[i]<mindistance&&!visited[i])
    {

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 && i==dst)
{
    printf("\nShortest path of node %d from %d:::",i,startnode,distance[i]);
    printf("\nPath=%d",i);

    j=i;
    do
    {
j=pred[j];
printf("<-%d",j);
    }while(j!=startnode);
    }
}

Comments

Popular posts from this blog

2D transformation for reflection in C program (Computer Graphics).

Program: #include<stdio.h> #include<conio.h> #include<graphics.h> #include<stdlib.h> void refx(int x1,int x2,int x3,int y1,int y2,int y3){ line(320,0,320,430); line(0,240,640,240); x1=(320-x1)+320; x2=(320-x2)+320; x3=(320-x3)+320; line(x1,y1,x2,y2); line(x2,y2,x3,y3); line(x3,y3,x1,y1); } void refy(int x1,int x2,int x3,int y1,int y2,int y3){ line(320,0,320,430); line(0,240,640,240); y1=(240-y1)+240; y2=(240-y2)+240; y3=(240-y3)+240; line(x1,y1,x2,y2); line(x2,y2,x3,y3); line(x3,y3,x1,y1); } void main() { int gd=DETECT,gm; int x1,y1,x2,y2,x3,y3; clrscr(); initgraph(&gd,&gm,"c://turboc3//bgi"); line(320,0,320,430); line(0,240,640,240); x1=150;y1=100; x2=220;y2=220; x3=220;y3=110; line(x1,y1,x2,y2); line(x2,y2,x3,y3); line(x3,y3,x1,y1); getch(); refx(x1,x2,x3,y1,y2,y3); getch(); refy(x1,x2,x3,y1,y2,y3); getch(); closegraph(); }

Write a c program for Merge short.

Solution: #include <stdio.h> #include<conio.h> #define max 10 int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 }; int b[11]; void merging(int low, int mid, int high) {    int l1, l2, i;    l1 = low;    l2 = mid + 1;    for(i = low; l1 <= mid && l2 <= high; i++) {       if(a[l1] <= a[l2])       { b[i] = a[l1]; l1++;       }       else          b[i] = a[l2++];    }        while(l1 <= mid)           b[i++] = a[l1++];    while(l2 <= high)          b[i++] = a[l2++];    for(i = low; i <= high; i++)       a[i] = b[i]; } void sort(int low, int high) {    int mid;        if(low < high) {       mid = (low + high) / 2;       sort(low, mid);       sort(mid+1, high);       merging(low, mid, high);    } else {        return;    }    } int main() {     int i;    printf("List before sorting\n");        for(i = 0; i <= max; i++)       printf("%d ", a[i]);    sort(0, max);