Code Floyds algorithm for shortest path
Hi . I need to code Floyds Algorithm that prints the optimal (shortest path) length between any 2 given vertices using c++ language .
Here's the algorithm that i want to code it :confused:
void floyd (int n , const number w[],number D[][],index P[][])
{
index i, j,k;
for(i=1;i<=n;i++)
for(j=1; j<=n;j++)
p[i][j]=0;
D=W;
for(k=1;k<=n;ki++)
for(i=1; i<=n;i++)
for(j=1; j<=n;j++)
if (D[i][k]+D[k][j]<D[i][j]){
p[i][j]=k;
D[i][j]=D[i][k]+ D[k][j];
}
}
# 1 Re: Code Floyds algorithm for shortest path
I think it miss 'print' and 'stop' , anyway where u have stoped , and what u can't continue ? , u just need to put a proper variable name , int, long , and so on .. and recognize the interface with the main function and calling this function ...
send us what u have tried and where u have stoped .
Amahdy at 2007-11-11 20:59:27 >
# 2 Re: Code Floyds algorithm for shortest path
its pretty close already.
you need to put types on these:
number types are int, float, double in c++
void floyd (int n , int *w, int **D, int **P)
{
int i, j,k;
for(i=1;i<=n;i++)
for(j=1; j<=n;j++)
p[i][j]=0;
D=W; //this statement is no good. You need to copy in a loop or use memcpy to move the elements over. Since the dimensions are different, I am not sure what you wanted, but it would just be another loop like the ones you have here.
for(k=1;k<=n;ki++)
for(i=1; i<=n;i++)
for(j=1; j<=n;j++)
if (D[i][k]+D[k][j]<D[i][j]){
p[i][j]=k;
D[i][j]=D[i][k]+ D[k][j];
}
}
jonnin at 2007-11-11 21:00:33 >
# 3 Re: Code Floyds algorithm for shortest path
Execuse me jonnin I don't meen anything at all,, just if he was asking about c++ implementation , and u try helping him by giving him the total code [not like I made to let him give a try] u think he will make the for loop and memcopy ? also (question for me) why u have changed to pointers and make life complex , it's the same with arrays as mentioned in the algorithm ,
and hence he will use w directly without d ...
I hope that u understand what I meen my friend , thank u.
Amahdy at 2007-11-11 21:01:26 >
# 4 Re: Code Floyds algorithm for shortest path
He already had the total code except for minor syntax changes from whatever that was to c++. The compiler would have told him most of what I did.
It does not matter what is in the header, the array dereference and pointer dereference are the same, and it removed many excess chars (extra long header) so I shortened [] to * multiple times for a shorter header. No extra complexity here, its not dynamic memory or "pointers" you see?
also you can pass
void foo(int *p)
an array as follows
int x[100];
foo(x); //this is fine...
given what he wrote, I think he can make the assignment loop for w and d, if not he can ask again. Its just more of the same.
Memcpy / memset are frowned upon these days because of objects, but to remove a double for loop and replace it with an operation that maps one to one on intel processor's assembly language (or closely, there are some sweet memory movement ops on the x86's) it makes sense to use it sometimes.
jonnin at 2007-11-11 21:02:27 >
