如何修改C++版Floyd-Warshall算法以支持输入小数？

Hey there! Since you're working with decimal values instead of integers, we'll need to adjust several key parts of the code to handle floating-point numbers. Let's break down the necessary changes step by step:

1. 替换整数类型为浮点类型 #

All variables and arrays storing weights or distances need to switch from int to double (this type handles both whole numbers and decimals with good precision):

• Change int w[MAX][MAX], d[MAX][MAX][MAX]; to double w[MAX][MAX], d[MAX][MAX][MAX];
• Keep index variables like i, j, k, v as int — they represent vertex counts, which are always integers.

2. 修改输入输出格式符 #

• For reading decimal values, replace %d in scanf with %lf (the format specifier for double).
• For printing decimal values, replace %d in printf with %lf (or %f — both work for doubles in printf, but %lf is more consistent).

3. 替换整数min函数为浮点版本 #

The standard min function (if even available here) won't work for doubles. You have two simple options:

Option 1: Use a ternary operator #

Replace the min call with a direct comparison:

d[k][i][j] = (d[k-1][i][j] < d[k-1][i][k] + d[k-1][k][j]) ? d[k-1][i][j] : d[k-1][i][k] + d[k-1][k][j];

Option 2: Write a custom min function for doubles #

Add this helper function before your floyd declaration:

double min(double a, double b) {
    return (a < b) ? a : b;
}

Then you can keep the original min call syntax.

4. （可选）移除过时的DOS函数 #

Note that conio.h, clrscr(), and getch() are outdated and not supported by most modern compilers (like GCC or Clang). If you're using a modern environment:

• Remove #include <conio.h>
• Replace clrscr(); with system("clear"); (Linux/macOS) or system("cls"); (Windows)
• Replace getch(); with getchar(); to wait for user input before exiting
• Change void main() to int main() and add return 0; at the end for standard C compliance

修改后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#define MAX 30

// Custom min function for doubles
double min(double a, double b) {
    return (a < b) ? a : b;
}

void floyd(int);
double w[MAX][MAX], d[MAX][MAX][MAX];

int main() {
    int i, j, v;
    // Uncomment below if you need screen clearing
    // system("clear"); // Use "cls" for Windows
    printf("Enter the number of vertices:\n");
    scanf("%d", &v);
    printf("Enter the weights (use decimals like 2.5, 0.0, etc.):\n");
    for(i = 1; i <= v; i++) {
        for(j = 1; j <= v; j++) {
            scanf("%lf", &w[i][j]);
        }
    }
    floyd(v);
    getchar();
    return 0;
}

void floyd(int v) {
    int k, i, j;
    k = 0;
    for(i = 1; i <= v; i++) {
        for(j = 1; j <= v; j++) {
            d[k][i][j] = w[i][j];
        }
    }
    for(k = 1; k <= v; k++) {
        for(i = 1; i <= v; i++) {
            for(j = 1; j <= v; j++) {
                d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]);
            }
        }
    }
    // Displaying matrix
    for(k = 0; k <= v; k++) {
        printf("k = %d\n", k);
        for(i = 1; i <= v; i++) {
            printf("\n");
            for(j = 1; j <= v; j++) {
                printf("\t%lf", d[k][i][j]);
                // Use "%.2lf" instead to show only 2 decimal places
            }
        }
        printf("\n\n");
    }
}

额外小提示 #

• When entering weights, you can input values like 1.5, 3.0, 0.75, etc.
• If you want cleaner output with fewer decimal places (e.g., 2 digits), replace %lf in the print statement with %.2lf.

内容的提问来源于stack exchange，提问作者Michael Perdana