Floyd

Posted on | Visitors:
问题描述

求无向图中各点之间的最短路径长度和对应的最短路径。如果有多条最短路径，给出一条即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#define MAXV 100 

int D[MAXV][MAXV] = {0};
int min_path[MAXV][MAXV] = {0};

void Floyd(int A[MAXV][MAXV], int n)
{
    int i, j, k;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        {
            min_path[i][j] = -1;
            if(i == j)
            {
                D[i][j] = 0;
                continue;
            }
            if(A[i][j])
            {
                D[i][j] = A[i][j];
            }
            else
            {
                D[i][j] = 99;   // a very large number, more than any of A[i][j]
            }
            
        }

    for (k = 0; k < n; k++)
    {
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                if (D[i][j] > (D[i][k] + D[k][j]))
                {
                    D[i][j] = D[i][k] + D[k][j];
                    min_path[i][j] = k;
                }
    }
}

// print shortest path from i to j
void print_shortest_path(int i, int j)
{
    printf("shortest path from %d to %d is  ", i, j);
    printf("%d ->", i);
    while(min_path[i][j] != -1)
    {
        printf(" %d ->", min_path[i][j]);
        i = min_path[i][j];
    }
    printf(" %d\n", j);
}

int main()
{
    int n = 7;
    int A[MAXV][MAXV] = {
        {0, 1, 0, 1, 1, 0, 0},
        {1, 0, 1, 1, 0, 0, 0},
        {0, 1, 0, 1, 1, 0, 0},
        {1, 1, 1, 0, 1, 0, 0},
        {1, 0, 1, 1, 0, 1, 0},
        {0, 0, 0, 0, 1, 0, 1},
        {0, 0, 0, 0, 0, 1, 0}
        };

    // shortest path
    Floyd(A, n);
    int a = 2;
    int b = 6;
    printf("shortest path length from %d to %d is %d\n", a, b, D[a][b]);
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            printf("shortest path length from %d to %d is %d\n", i, j, D[i][j]);        
            // print_shortest_path(i, j);
        }
    }

    return 0;
}