DataStruct/ShortestPath_floyd.cpp at master · githubdlj/DataStruct · GitHub

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
84
85
86
87
88
/********************************************************************
	Time:	  2015/11/10
	Filename: ShortestPath_floyd
	Author:	  dinglj

	Purpose:  顶点对最短路径，有向网
              时间复杂度 O(n ^ 3)
*********************************************************************/
#define INF     65536
#define MAXSIZE 20

//////////////////////////////////////////////////////////////////////
//  邻接矩阵存储结构
typedef struct
{
    int no;
    char info;
}VertexType;

typedef struct
{
    int weight;
}EdgeType;

typedef struct
{
    VertexType v[MAXSIZE];
    EdgeType e[MAXSIZE][MAXSIZE];

    int vertexNum;
    int edgeNum;
}MGraph;

//////////////////////////////////////////////////////////////////////
/********************************************************************
	Method:    ShortestPath_floyd
	Parameter:
	Returns:

	Purpose:   求任意一对顶点之间的距离

*********************************************************************/
//  辅助存储结构, 存储距离
int dist[MAXSIZE][MAXSIZE];

//  辅助存储结构，存储路径
int path[MAXSIZE][MAXSIZE];

//////////////////////////////////////////////////////////////////////
void ShortesPath_floyd(MGraph G)
{
    //  初始化辅助存储结构
    for (int i = 0; i < G.vertexNum; ++i)
    {
        for (int j = 0; j < G.vertexNum; ++j)
        {
            dist[i][j] = G.e[i][j].weight;
            path[i][j] = -1;        //  path = -1既可以表示直达，也可表示不可到达，要看dist是否为INF
        }
    }

    //
    for (int k = 0; k < G.vertexNum; ++k)
    {
        for (int i = 0; i < G.vertexNum; ++i)
        {
            for (int j = 0; j < G.vertexNum; ++j)
            {
                if (dist[i][j] > dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

//  输出路径<start, end>路径之间的点
void PrintPath(int start, int end)
{
    if (-1 != path[start][end])
    {
        PrintPath(start, path[start][end]);     //  输出start到k之间的点
        printf("%d\t", path[start][end]);       //  输出k
        PrintPath(path[start][end], end);       //  输出k到end之间的点
    }
}