所有点之间的最短路径问题，弗洛伊德·沃歇尔

Question

先生。罗文计划徒步旅行 巴黎的。然而，由于他是一个 小懒，他想拿 遍历所有路径的最短路径 他想去的地方。他计划 乘坐巴士到第一个地点 又一个从最后一个地方回来， 所以他可以自由选择首发 和结束地点。你能帮助他吗？

输入

第一行输入包含 参观地点的数量（n）。然后， 在接下来的n行中，你会发现 每个游览地点的坐标。 这是一个例子：

<块引用>

3

132 73

49 86

72111

输出

对于每个测试用例，您的程序 应该输出一行包含 罗文先生必须的最小距离 步行参观所有地方假设 从一个地方到一个地方的步行距离 另一个是欧几里德距离。这 算法应该输出一个数字 恰好为 3 的定点表示法 小数点右边的数字 点且无前导空格。有 最多可游览 12 个地点。示例

输入示例：

<块引用>

3

132 73

49 86

72111

示例输出：

<块引用>

104.992

我一直在为我的家庭作业编写这段代码，但我无法让它工作，我开始想知道这是否是最好的方法..

问题是 floyd-warshall 函数，它对 float **path 结构没有任何作用..不知道为什么.. floydwarshall(path, n, next); 之前和之后的路径是相同的

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <float.h>

/*Implementing of http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm*/


struct point {
    float x;
    float y;
};


float cost(struct point* a, struct point* b) {

    return sqrt(pow((*a).x - (*b).x, 2) + pow((*a).y - (*b).y, 2));

}


float** f2dmalloc(int n, int m){

    int i;
    float **ptr;

    ptr = malloc(n * sizeof(float *));
    for (i = 0; i < n; i++) {
        ptr[i] = calloc(m, sizeof(float));
    }

    return ptr;

}



void floydwarshall(float **path, int n, float ** next){
    int i, j, k;
    float a, b;
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                a = path[i][j];
                b = path[i][k] + path[k][j];
                path[i][j] = ((a) < (b) ? a : b);
                next[i][j] = k;

            }
        }
    }

}

int main (int argc, const char* argv[])
{



    int i;
    int j;
    int n;

    float temp;
    float mininum;

    scanf("%d", &n);

    /*
    A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
    from i to j using intermediate vertices (1..k−1).  Each path[i][j] is initialized to
    cost(i,j).
    */
    float ** path;
    float ** next;
    struct point* points;

    path = f2dmalloc(n, n);
    next = f2dmalloc(n, n);

    points = malloc(n * sizeof(struct point));

    for (i = 0; i < n; i++){
        scanf("%f %f", &(points[i].x), &(points[i].y));
    }


    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            path[i][j] = cost(&points[i], &points[j]);
        }
    }


    temp = 0;
    for (i = 0; i < n; i++) {
        mininum = FLT_MAX;
        for (j = 0; j < n; j++) {
            printf("%.3f\t", path[i][j]);
            if (path[i][j] < mininum && path[i][j] != 0){
                mininum = path[i][j];
            }

        }
        printf("\tminimum - %.3f\n", mininum);
        temp += mininum;
    }

    floydwarshall(path, n, next);


    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%.3f\t", next[i][j]);

        }
        printf("\n");
    }

    /*
    temp = 0;
    for (i = 0; i < n; i++) {
        mininum = FLT_MAX;
        for (j = 0; j < n; j++) {
            printf("%.3f\t", path[i][j]);
            if (path[i][j] < mininum && path[i][j] != 0){
                mininum = path[i][j];
            }

        }
            printf("\tminimum - %.3f\n", mininum);
        temp += mininum;
    }

    printf("%.3f\n", temp);

     */

    return 0;
}

Answer 1

Floyd-Warshall 解决了这个问题：对于每对点，找到连接它们的最短路径。 （它需要连接这两点。它不需要做任何其他事情。如果产生更短的路径，它只会访问其他点。）

在目前的情况下，因为您总是可以直接从任何点到任何其他点，最短路径始终是直接路径：只需从 A 到 B。（这就是为什么调用 floydwarshall 不会改变任何内容。）

但是您要解决的问题似乎是旅行商问题：找到一条访问所有点且尽可能短的路径。

这些是完全不同的问题，您需要做一些完全不同的事情来解决您被要求解决的问题。