Solved

# Floyd's Algorithm

Posted on 1997-12-16

Hi, I am studing Floyd's Algorithm and I want to implement it by using C. However, somehow, I just get stuck in there. I want to use that program to read a list of data from stdin and then write a matrix which shows each of the shorest path.

i.e. If I have the input,

A B 24 F 28

B A 24 C 11

C B 11 D 13

D C 13 E 20 F 12

E D 20 F 15

F A 28 D 12 E 15

I want to have :

A B C D E F

A 0 24 35 40 43 28

B 24 0 11 24 44 36

C 35 11 0 13 33 25

D 40 24 13 0 20 12

E 43 44 33 20 0 15

F 28 36 25 12 15 0

as the output.

here is the algorithm I am going to use, but I never know how to bring them together.

NODE u,v,w;

for(v=0;v<MAX;v++)

for(w=0;w<MAX;w++)

dist[v][w]=arc[v][w];

for(u=0;u<MAX;u++)

for(v=0;v<MAX;v++)

for(w=0;w<MAX;w++)

if (dist[v][u]+dist[u][w] <dist[v][w])

dist[v][w]=dist[v][u]+dist[u][w];

If have did that problem before, or know to how implement it , just let me know.

thanks,