DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

Thread: The main for Floyd's Algorithm Code

1. Registered User
Join Date
Jan 2007
Posts
2

The main for Floyd's Algorithm Code

Hi
I have this Floyd's Algorithm Code, Can you help me to write the main for this function .

#include "stdinc.h"
#include "wdigraph.h"

void floyd(wdigraph& G, int* dist[], vertex* mid[]) {
// Compute a solution to the all pairs shortest path problem
// using Floyd's algorithm. Return dist[u][v]=distance from u to v
// and mid[u][v]=an intermediate mid-point of the shortest u-v path.

vertex u,v,w; edge e;

// Initialize dist and mid.
for (u = 1; u <= G.n; u++) {
for (v = 1; v <= G.n; v++) {
if (u == v) dist[u][v] = 0;
else dist[u][v] = BIGINT;
mid[u][v] = Null;
}
}
for (u = 1; u <= G.n; u++) {
for (e = G.firstout(u); e != Null; e = G.nextout(e)) {
dist[u][v] = G.w(e);
}
}

// Compute distances.
for (v = 1; v <= G.n; v++) {
if (dist[v][v] < 0) fatal("floyd: negative cycle");
for (u = 1; u <= G.n; u++) {
for (w = 1; w <= G.n; w++) {
if (dist[u][v] != BIGINT && dist[v][w] != BIGINT
&& dist[u][w] > dist[u][v] + dist[v][w]) {
dist[u][w] = dist[u][v] + dist[v][w];
mid[u][w] = v;
}
}
}
}
}
Last edited by comp_student; 01-15-2007 at 06:04 PM.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts

 FAQ Latest Articles Java .NET XML Database Enterprise