Djikstra's algo

[Suzanne]

Can ay1 pls provide me the sample code 4 a basic Dijkstra algo? I understand how the algo works but need help to know where to start. Thanx.

[Galik]

Wikipedia gives pseudocode:

http://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode

[Suzanne]

I am actually looking for a working sample program. Some basic program I can use as a starting point then adapt.

[Bazzy]

All you need to do is converting the pseudocode in C++ syntax

[Galik]

The best way to learn is to try to write the program yourself. Then if you post the code here we can try to help you fix it.

[Suzanne]

Actually the problem is with my Code blocks( I am working on an Ubuntu platform) compiler. Its not recognizing my libraries. This causes errors when I try to build.

Errors:
/home/Desktop/test/Djikstra2.cpp|5|error: conio.h: No such file or directory|
/home/Desktop/test/Djikstra2.cpp|6|error: graphics.h: No such file or directory|
/home/Desktop/test/Djikstra2.cpp|7|error: dos.h: No such file or directory|
/home/Desktop/test/Djikstra2.cpp|13|error: ‘::main’ must return ‘int’|
/home/Desktop/test/Djikstra2.cpp||In function ‘int main()’:|
/home/Desktop/test/Djikstra2.cpp|15|error: ‘DETECT’ was not declared in this scope|
/home/Desktop/test/Djikstra2.cpp|16|error: ‘clrscr’ was not declared in this scope|

Libraries Included:
#include<conio.h>
#include<graphics.h>
#include<dos.h>

[Galik]

Those look like windows (DOS) libraries. The code you have probably needs to be ported to Linux.

[Bazzy]

they are all quite old and shouldn't be used at all

[Suzanne]

But what's wrong with including a library like <conio.h> ? I have used it before, dunno why its showing errors now.

[Bazzy]

_{http://en.wikipedia.org/wiki/Conio.h} :

conio.h is a C header file used in old MS-DOS compilers to create text user interfaces. It is not described in The C Programming Language book, and it is not part of the C standard library, ISO C nor is it required by POSIX.

I bet that you are not writing a TUI for DOS, thus you don't need it

[Suzanne]

Ok but why does it not recognise the other header files? It doesn't recognise my cin statements either. Code blocks is always so buggy. I will try debugging again.

[Galik]

Why don't you post your code here?

Everything you include from the standard libraries like <iostream> need std:: prefixed to them like this:

std::cout << "some ftuff" << std::endl;

[Suzanne]

#include<iostream>
#include<stdio.h>
#include<conio.h>
#include<graphics.h>
#include<dos.h>
using namespace std;

float sum=0,w=0,s,wn,v[8],td=0,e,i,j,n,w1[8],j1[8],arr[8],arr1[8],e1,count,d2,y1;
float var,a[8][8],d[8],p[8],n1,c,c1,w2;
int main()
{
int gd=DETECT,gm;
clrscr();
void draw(float,float);
void dijkstra(float s,float e,float v1[8],float d1[8],float p1[8],float
a1[8][8],float n);
void ssp();
void path();
void initial();
printf("There are 8 routers in each subnet");
n=8;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
a[i][j]=32767;
}
}
printf("Enter the weight between 0 & 1 : ");
scanf("%f",&a[0][1]);
a[1][0]=a[0][1];
printf("Enter the weight between 0 & 3 : ");
scanf("%f",&a[0][3]);
a[3][0]=a[0][3];
printf("Enter the weight between 1 & 5 : ");
scanf("%f",&a[1][5]);
a[5][1]=a[1][5];
printf("Enter the weight between 1 & 2 : ");
scanf("%f",&a[1][2]);
a[2][1]=a[1][2];
printf("Enter the weight between 2 & 4 : ");
scanf("%f",&a[2][4]);
a[4][2]=a[2][4];
printf("Enter the weight between 2 & 3 : ");
scanf("%f",&a[2][3]);
a[3][2]=a[2][3];
printf("Enter the weight between 3 & 7 : ");
scanf("%f",&a[3][7]);
a[7][3]=a[3][7];
printf("Enter the weight between 4 & 5 : ");
scanf("%f",&a[4][5]);
a[5][4]=a[4][5];
printf("Enter the weight between 4 & 7 : ");
scanf("%f",&a[4][7]);
a[7][4]=a[4][7];
printf("Enter the weight between 5 & 6 : ");
scanf("%f",&a[5][6]);
a[6][5]=a[5][6];
printf("Enter the weight between 6 & 7 : ");
scanf("%f",&a[6][7]);
a[7][6]=a[6][7];
printf("Enter source and destination node from network 1 ");
scanf("%f %f",&s,&e);
clrscr();//ERROR
initgraph(&gd,&gm,"c:\tc\bgi");
setcolor(WHITE);
fillellipse(20,100,7,7);fillellipse(85,50,7,7);//ERROR
fillellipse(150,100,7,7);fillellipse(85,150,7,7);
fillellipse(320,100,7,7);fillellipse(385,50,7,7);
fillellipse(450,100,7,7);fillellipse(385,150,7,7);
w1[0]=20;w1[1]=85;w1[2]=150;w1[3]=85;w1[4]=320;
w1[5]=385;w1[6]=450;w1[7]=385;
j1[0]=100;j1[1]=50;j1[2]=100;j1[3]=150;j1[4]=100;j1[5]=50;
j1[6]=100;j1[7]=150;
initial();
setcolor(GREEN);
for(i=0;i<n;i++)
{
v[i]=32767;
d[i]=32767;
p[i]=0;
}
w=s;
d[s]=0;
v[s]=s;
td=0;
dijkstra(s,e,v,d,p,a,n);
path();
c=w1[e];
c1=j1[e];
printf("One more packet ?(Type 1 if yes) ");
scanf("%f",&count);
path();
if(count==1)
ssp();
path();
w=e;
setcolor(GREEN);
count=0;
printf("Enter source and destination node from network 2 ");
scanf("%f %f",&s,&e);
a[0][1]=2;
a[0][3]=6;
a[1][2]=2;
a[1][5]=7;
a[2][3]=1;
a[2][4]=2;
a[4][5]=3;
a[5][6]=3;
a[4][7]=2;
a[6][7]=2;
a[3][7]=4;
a[1][0]=2;
a[3][0]=6;
a[2][1]=2;
a[5][1]=7;
a[3][2]=1;
a[4][2]=2;
a[5][4]=3;
a[6][5]=3;
a[7][4]=2;
a[7][6]=2;
a[7][3]=4;
setcolor(WHITE);
fillellipse(20,400,7,7);fillellipse(85,350,7,7);
fillellipse(150,400,7,7);fillellipse(85,450,7,7);
fillellipse(320,400,7,7);fillellipse(385,350,7,7);
fillellipse(450,400,7,7);fillellipse(385,450,7,7);
w1[0]=20;w1[1]=85;w1[2]=150;w1[3]=85;w1[4]=320;
w1[5]=385;w1[6]=450;w1[7]=385;
j1[0]=400;j1[1]=350;j1[2]=400;j1[3]=450;j1[4]=400;j1[5]=350;
j1[6]=400;j1[7]=450;
initial();
setcolor(GREEN);
for(i=0;i<n;i++)
{
v[i]=32767;
d[i]=32767;
p[i]=0;
}
w=s;
d[s]=0;
v[s]=s;
td=0;
line(c,c1,w1[s],j1[s]);
delay(2000);
dijkstra(s,e,v,d,p,a,n);
path();
if(count==1)
ssp();
path();
getch();
}
void dijkstra(float s,float e,float v1[8],float d1[8],float p1[8],float a1[8][8],float n)
{
while((p1[e])==0)
{
for(i=0;i<n;i++)
{
if((a1[w][i]+td)<d1[i]&&i!=w&&a1[w][i]!=32767)
{
d1[i]=a1[w][i]+td;
d2=d1[i];
v1[i]=w;
}}
sum=32767;
for(i=0;i<n;i++)
{
if(d1[i]<sum&&i!=s&&p1[i]!=1)
{
sum=d1[i];
wn=i;
}}
p1[wn]=1;
td=d1[wn];
w=wn;
}
}
void draw(float w,float v1)
{
float s,x,y;
s=(j1[v1]-j1[w])/(w1[v1]-w1[w]);
if(s<0)
s=s*-1;
x=w1[w];
y=j1[w];
moveto(x,y);
if(x==w1[v1])
{
while(y!=j1[v1])
{
if(y>j1[v1])
{
line(x,y,x,y-1);
delay(10);
y=y-1;
}
else
{
line(x,y,x,y+1);
delay(10);
y=y+1;
}}}
if(y==j1[v1])
{
while(x!=w1[v1])
{
if(x>w1[v1])
{
line(x,y,x-1,y);
delay(10);
x=x-1;
}
else
{
line(x,y,x+1,y);
delay(10);
x=x+1;
}}}
if(x<w1[v1]&&y<j1[v1])
{
while(x!=w1[v1])
{
line(x,y,x+1,y+s);
delay(10);
x=x+1;
y=y+s;
}}
if(x>w1[v1]&&y>j1[v1])
{
while(x!=w1[v1])
{
line(x,y,x-1,y-s);
delay(10);
x=x-1;
y=y-s;
i=i+1;
}}
if(x>w1[v1]&&y<j1[v1])
{
while(x!=w1[v1])
{
line(x,y,x-1,y+s);
delay(10);
x=x-1;
y=y+s;
i=i+1;
}}
if(x<w1[v1]&&y>j1[v1])
{
while(x!=w1[v1])
{
line(x,y,x+1,y-s);
delay(10);
x=x+1;
y=y-s;
i=i+1;
}
}}
void ssp()
{
d2=y1=32767;
setcolor(RED);
e1=e;
for(i=0;i<n;i++)
{
arr1[i]=v[i];
arr[i]=v[i];
}
while(e1!=s)
{
var=a[e1][arr1[e1]]=a[arr1[e1]][e1];
a[e1][arr1[e1]]=a[arr1[e1]][e1]=32767;
for(i=0;i<n;i++)
{
v[i]=32767;
d[i]=32767;
p[i]=0;
}
w=s;d[s]=0;
v[s]=s;
td=0;
dijkstra(s,e,v,d,p,a,n);
if(d2<y1)
{
y1=d2;
for(i=0;i<n;i++)
arr[i]=v[i];
}
a[e1][arr1[e1]]=a[arr1[e1]][e1]=var;
e1=arr1[e1];
}}
void path()
{
while(w!=s)
{
if(count==0)
{
draw(w,v[w]);
w=v[w];
}
else
{
draw(w,arr[w]);
w=arr[w];
}}}
void initial()
{
line(w1[0],j1[0],w1[1],j1[1]);
line(w1[0],j1[0],w1[3],j1[3]);
line(w1[1],j1[1],w1[5],j1[5]);
line(w1[1],j1[1],w1[2],j1[2]);
line(w1[2],j1[2],w1[4],j1[4]);
line(w1[2],j1[2],w1[3],j1[3]);
line(w1[3],j1[3],w1[7],j1[7]);
line(w1[4],j1[4],w1[5],j1[5]);
line(w1[4],j1[4],w1[7],j1[7]);
line(w1[5],j1[5],w1[6],j1[6]);
line(w1[6],j1[6],w1[7],j1[7]);
}

return 0;
} 

[Suzanne]

It doesn't recognize the arrays also.

[Galik]

That requires a graphics library. Is it required to give graphical output? Or do you just want the algorithm?

[z05DSL3A]

The problem with the arrays would seem to be that you defined i, j, s... as float.
there are numerous other problems with the code.

[Suzanne]

@Galik: I need the graphical output from this algo.
@Grey Wolf: Could u specify some of the other errors so that I will have a better idea of how to go about this.

[Galik]

Then you need to find a Linux friendly graphics library. That's going to be a learning curve. You might want to look at SDL and SDL_gfx.