c - 所有点之间的最短路径问题，floyd warshall

Question

Mr. Rowan plans to make a walking tour of Paris. However, since he is a little lazy, he wants to take the shortest path that goes through all the places he wants to visit. He plans to take a bus to the first place and another one back from the last place, so he is free to choose the starting and ending places. Can you help him?

Input

The first line of input contains the number of places to visit (n). Then, in the following n lines, you find the coordinates of each place to visit. Here is an example:

3

132 73

49 86

72 111

输出

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

示例输入:

3

132 73

49 86

72 111

示例输出:

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 的原因不会改变任何东西。)

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

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