LetUsCPlusPlus/DIJKWITH.CPP at main · Balaji4/LetUsCPlusPlus · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<time.h>
#include<dos.h>
int n,a[10][10],d[10],p[10],sr,ds;
void read();
void print();
void optimal(int src,int dest);


void optimal(int src,int dest)
{
int i,j,u,v,min;
int s[10];
for(i=0;i<n;i++)
 {
 d[i]=a[src][i];
 s[i]=0;
 p[i]=src;
 }
for(i=1;i<n;i++)
 {
 min=9999;
 u=-1;
 for(j=0;j<n;j++)
 {
   if(s[j]==0)
   {
     if(d[j]<min)
     {
      min=d[j];
      u=j;
     }
   }
 }
 s[u]=1;
 if(u==dest)
 return;
 for(v=0;v<n;v++)
 {
 if(s[v]==0)
  {
  if(d[u]+a[u][v]<d[v])
  {
  d[v]=d[u]+a[u][v];
  p[v]=u;
  }
 }
 delay(1);
}
}
}
void read()
{
int i,j;
printf("\n Enter the no. of nodes\n");
scanf("%d",&n);
printf("\n Enter the cost adjacency matrix [enter 9999 if path does not exist] \n");
for(i=0;i<n;i++)
 {
 for(j=0;j<n;j++)
 {
 scanf("%d",&a[i][j]);
 }
 }
 printf("enter the source \n");
 scanf("%d",&sr);
// printf("enter the destination\n");
 //scanf("%d",&ds);
}

void print()
{
int srce=sr-1,desti/*=ds-1*/,i;
// for(srce=0;srce<n;srce++)
// {
  for(desti=0;desti<n;desti++)
  {
   optimal(srce,desti);
   if(d[desti]==9999)
   printf("\n %c is not reachable from %c\n",desti+65,srce+65);
   else
   {
     printf("\n The shortest path is ");
     i=desti;
     while(i!=srce)
     {
      printf("%c <--",i+65);
      i=p[i];
     }
    printf("%c=%d\n",i+65,d[desti]);
   }
  }
// }
}

 void main()
 {
 clrscr();
 clock_t s,e;
 read();
 s=clock();
 delay(200);
 print();
 e=clock();
 printf("Time taken to execute=%lf",(e-s)/CLK_TCK);
 getch();
 }