DataStruct/ShortestPath_dijkstra.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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/******************************************************************************
	Time:	  2015/11/10
	Filename: ShortestPath_dijkstra
	Author:	  dinglj

	Purpose:  单源最短路径，有向网
              邻接矩阵实现
              时间复杂度 O(n ^ 2)
*********************************************************************/
#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_dijkstra
	Parameter:
	Returns:

	Purpose:   单源最短路径，邻接矩阵

*********************************************************************/
//  辅助存储结构, 存储路径，作用相当于MST_prim算法中的closedge
//  path[j] = {i, d}表示起点v到j的距离为d，且j的前驱为i
typedef struct
{
    int pre;      //    前驱
    int dist;     //    总距离
}Path;
Path path[MAXSIZE];

//  辅助存储结构，存储已经寻找到的点U集合, 作用相当于MST_prim算法中closedge.lowcost = 0
//  vSet[i] = true表示已经将i点纳入到集合U
bool vSet[MAXSIZE];

//////////////////////////////////////////////////////////////////////
void ShortestPath_dijkstra(MGraph G, int v)
{
    //  初始化path,vSet
    for (int vertexNo = 0; vertexNo < G.vertexNum; ++vertexNo)
    {
        path[vertexNo].pre = v;
        path[vertexNo].dist = G.e[v][vertexNo].weight;

        vSet[vertexNo] = false;
    }

    //  将v加入到顶点集合U
    vSet[v] = true;

    path[v].pre = -1;
    path[v].dist = 0;

    //  将剩余n - 1个点加入
    for (int index = 0; index < G.vertexNum - 1; ++index)
    {
        int minDist = INF;
        int minIndex = 0;
        //  从结合V - U中找到最短的距离
        for (int vertexNo = 0; vertexNo < G.vertexNum; ++vertexNo)
        {
            if (false == vSet[vertexNo] && path[vertexNo].dist < minDist)
            {
                minDist = path[vertexNo].dist;
                minIndex = vertexNo;
            }
        }

        //  将minIndex点加入集合U
        vSet[minIndex] = true;

        //  更新dist
        for (int vertexNo = 0; vertexNo < G.vertexNum; ++vertexNo)
        {
            //  此处是与MST_prim逻辑上的区别！
            //  可以不进行vSet判断，类似于MST_prim
            if ( (false == vSet[vertexNo]) && (path[minIndex].dist + G.e[minIndex][vertexNo].weight < path[vertexNo].dist))
            {
                path[vertexNo].dist = path[minIndex].dist + G.e[minIndex][vertexNo].weight;
                path[vertexNo].pre = minIndex;
            }
        }
    }
}

//  逆序输出路径信息起始点v到终点end的路径信息
void PrintPath(int end)
{
    printf("%d\n", path[end].dist);
    while (path[end].pre != -1)
    {
        printf("%d\t", end);
        end = path[end].pre;
    }
}