목차
<< routing algorithm >>
<< data >>
<< shortest_path >>
<< data >>
<< shortest_path >>
본문내용
j] = W[i][j];
// Searching for length & path
for(k = 0; k <= n - 1; k++) // node on path
for(i = 0; i <= n - 1; i++) // source
for(j = 0; j <= n - 1; j++) // destination
if(D[i][k] + D[k][j] < D[i][j]) {
P[i][j] = k + 1;
D[i][j] = D[i][k] + D[k][j];
}
}
// to print the result
void output(FILE *ofp)
{
int i, j;
for(i = 0; i <= n - 1; i++)
{
fprintf(ofp, "From source node %d:\n", i + 1);
fprintf(ofp, " D length path\n");
for(j = 0; j <= n - 1; j++)
if(i != j)
{
fprintf(ofp, " %d %2d %d -> ", j + 1, D[i][j], i + 1);
path(i + 1, j + 1, ofp);
fprintf(ofp, "%d\n", j + 1);
}
}
fprintf(ofp, "\n");
}
// to print nodes on path
void path(int q, int r, FILE *ofp)
{
if(P[q - 1][r - 1] != 0) {
path(q, P[q - 1][r - 1], ofp);
fprintf(ofp, "%d -> ", P[q - 1][r - 1]);
path(P[q - 1][r - 1], r, ofp);
}
}
// Searching for length & path
for(k = 0; k <= n - 1; k++) // node on path
for(i = 0; i <= n - 1; i++) // source
for(j = 0; j <= n - 1; j++) // destination
if(D[i][k] + D[k][j] < D[i][j]) {
P[i][j] = k + 1;
D[i][j] = D[i][k] + D[k][j];
}
}
// to print the result
void output(FILE *ofp)
{
int i, j;
for(i = 0; i <= n - 1; i++)
{
fprintf(ofp, "From source node %d:\n", i + 1);
fprintf(ofp, " D length path\n");
for(j = 0; j <= n - 1; j++)
if(i != j)
{
fprintf(ofp, " %d %2d %d -> ", j + 1, D[i][j], i + 1);
path(i + 1, j + 1, ofp);
fprintf(ofp, "%d\n", j + 1);
}
}
fprintf(ofp, "\n");
}
// to print nodes on path
void path(int q, int r, FILE *ofp)
{
if(P[q - 1][r - 1] != 0) {
path(q, P[q - 1][r - 1], ofp);
fprintf(ofp, "%d -> ", P[q - 1][r - 1]);
path(P[q - 1][r - 1], r, ofp);
}
}