shortest path between all points problem, floyd warshall

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

Output

For each test case, your program should output one line containing the minimum distance that Mr. Rowan must walk to visit all places assuming that the walking distance from one place to another is the Euclidean distance. The algorithm should output a number in fixed-point notation with exactly 3 digits to the right of the decimal point and no leading space. There are at most 12 places to visit. Example

Example input:

3

132 73

49 86

72 111

Example output:

104.992

i've been working on this code, for my homework, but i cant make it work, im start wondering if this is the best approach..

the problem is the floyd-warshall function, that does nothing on float **path structure.. dont know why.. path is the same before and after the 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;
}

Floyd-Warshall solves the problem: For each pair of points, find the shortest path joining them. (It needs to join these two points. It doesn't need to do anything else. It will only visit other points if that produces a shorter path.)

In the present case, since you can always go directly from any point to any other, the shortest path is always the direct one: just go from A to B. (Which is why calling floydwarshall doesn't change anything.)

But the problem you're trying to solve seems to be the travelling salesman problem: find a path that visits all your points and is as short as possible.

These are entirely different problems, and you'll need to do something quite different to solve the problem you've been asked to solve.