浙大陈越何钦铭数据结构07-图6 旅游规划【最小堆实现】

题目：

题目和浙大陈越何钦铭数据结构07-图6 旅游规划是一样的，不同的是用最小堆实现函数【FindMinDist】。

时间复杂度对比：
浙大陈越何钦铭数据结构07-图6 旅游规划：
创建图（CreateGraph）：时间复杂度为O(N^2)，因为需要使用两层循环初始化邻接矩阵。
插入边（InsertEdge）：时间复杂度为O(1)，因为只是将边的距离和代价插入到邻接矩阵中。
构建图（BuildGraph）：时间复杂度为O(E)，其中E为边的个数。需要进行E次的边的插入操作。
查找未被收录顶点中dist最小者（FindMinDist）：时间复杂度为O(N)，需要遍历所有未收录的顶点，查找其中dist最小的顶点。
Dijkstra算法主循环：时间复杂度为O(N^2)，每次循环都需要找到未收录顶点中dist最小的顶点，并更新其周围顶点的dist和cost值。
综上所述，整个算法的时间复杂度为O(N^2)。

堆实现代码：
如果将 FindMinDist 函数使用最小堆实现，会使得 Dijkstra 算法的时间复杂度变为 O((N + E)logN)，其中 N 为顶点数，E 为边数。
具体分析如下：
创建图（CreateGraph）：时间复杂度仍为 O(N^2)，与之前相同。
插入边（InsertEdge）：时间复杂度仍为 O(1)，与之前相同。
构建图（BuildGraph）：时间复杂度仍为 O(E)，与之前相同。
查找未被收录顶点中dist最小者（FindMinDist）：使用最小堆实现后，每次查找最小值的时间复杂度为 O(logN)，总共需要进行 N 次查找，因此时间复杂度为 O(NlogN)。
Dijkstra算法主循环：在每个节点更新最短路径时，需要将其邻接节点的信息插入最小堆中，插入一个节点的时间复杂度为 O(logN)，总共需要插入 E 个节点，因此时间复杂度为 O(ElogN)。同时，在每个节点更新最短路径时，还需要进行一次堆操作，将堆中的最小值取出，时间复杂度为 O(logN)，总共需要进行 N 次堆操作，因此时间复杂度为 O(NlogN)。
综上所述，使用最小堆实现的 Dijkstra 算法的时间复杂度为 O((N + E)logN)。相比于之前的 O(N^2)，当图的规模较大时，使用最小堆可以提高算法的效率。

代码：

#include 
#include 
#include 

#define MAX_VERTEX_NUM 500
#define MAX_DIST 501
#define MAX_COST 501
#define ERROR -1
#define MIN_DATA -1000

typedef int ELEMENT_TYPE;
typedef int Vertex;

struct _MinHeap
{
    ELEMENT_TYPE *Elements;
    int Size;
    int Capacity;
};
typedef struct _MinHeap *MinHeap;

struct _Edge
{
    Vertex V, W;
    int dist, cost;
};
typedef struct _Edge *Edge;

struct _MGraph
{
    int Nv, Ne;
    int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int cost[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
};
typedef struct _MGraph *MGraph; /* 以邻接矩阵存储的图的类型  */

void InsertEdge(MGraph G, Edge E); // 插入边
MGraph CreateGraph(int vertexNum); // 初始化图
MGraph BuildGraph();

bool isEmpty(MinHeap H);
bool isFull(MinHeap H);
void PercUp(MinHeap H, int p, int dist[]);
ELEMENT_TYPE DelMin(MinHeap H, int dist[]);
void FreeHeap(MinHeap H);
MinHeap CreateHeap(int MaxSize);
void BuildMinHeap(MinHeap H, int dist[]);

Vertex FindMinDist(MinHeap H, int dist[]);
void Dijkstra(MGraph G, int dist[], int cost[], Vertex S);

Vertex src, dst;
// 对于全局的int数组自动初始化为0，bool数组初始化为false
int dist[MAX_VERTEX_NUM];
int cost[MAX_VERTEX_NUM];
bool collected[MAX_VERTEX_NUM];

/*
07-图6 旅游规划
难度：3颗星

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

3 40
 */

int main()
{
    MGraph G = BuildGraph();
    Dijkstra(G, dist, cost, src);
    printf("%d %d\n", dist[dst], cost[dst]);

    return 0;
}

MGraph CreateGraph(int vertexNum)
{
    MGraph G = (MGraph)malloc(sizeof(struct _MGraph));
    G->Nv = vertexNum;
    G->Ne = 0;
    Vertex V, W;

    for (V = 0; V < vertexNum; V++)
    {
        for (W = 0; W < vertexNum; W++)
        {
            G->dist[V][W] = MAX_DIST;
            G->cost[V][W] = MAX_COST;
        }
    }

    return G;
}

void InsertEdge(MGraph G, Edge E)
{
    /* 插入边 */
    G->dist[E->V][E->W] = E->dist;
    G->cost[E->V][E->W] = E->cost;

    /* 若是无向图则要反向也插入 */
    G->dist[E->W][E->V] = E->dist;
    G->cost[E->W][E->V] = E->cost;
}

MGraph BuildGraph()
{
    MGraph G;
    Edge E;
    int Nv, Ne;
    scanf("%d %d %d %d", &Nv, &Ne, &src, &dst);
    G = CreateGraph(Nv);
    if (Ne)
    {
        G->Ne = Ne;
        E = (Edge)malloc(sizeof(struct _Edge));

        for (int i = 0; i < G->Ne; i++)
        {
            scanf("%d %d %d %d", &E->V, &E->W, &E->dist, &E->cost);
            InsertEdge(G, E);
        }

        free(E);
    }

    return G;
}

Vertex FindMinDist(MinHeap H, int dist[])
{
    Vertex minV = ERROR;
    // 从堆中取出最小值，并维护最小堆的有效性。
    minV = DelMin(H, dist);
    
    return minV;
}

void Dijkstra(MGraph G, int dist[], int cost[], Vertex S)
{
    Vertex V, W;

    /* 初始化：此处默认邻接矩阵中不存在的边用INFINITY表示 */
    for (V = 0; V < G->Nv; V++)
    { // dist和cost分别保存的是源点到顶点V的距离和开销
        dist[V] = G->dist[S][V];
        cost[V] = G->cost[S][V];
    }
    /* 先将起点收入集合 */
    dist[S] = 0;
    cost[S] = 0;
    collected[S] = true;

    // 根据dist对未收录顶点创建最小堆
    MinHeap H = CreateHeap(MAX_VERTEX_NUM);

    for (V = 0; V < G->Nv; V++)
    {
        if (collected[V] == false)
        { // H->Elements保存的是未收集顶点的编号，本例依次是1,2,3
            H->Elements[++H->Size] = V;
        }
    }

    BuildMinHeap(H, dist);

    while (1)
    {
        /* V = 未被收录顶点中dist最小者 */
        V = FindMinDist(H, dist);
        if (V == ERROR)      /* 若这样的V不存在 */
            break;           /* 算法结束 */
        collected[V] = true; /* 收录V */

        for (W = 0; W < G->Nv; W++) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未被收录 */
            if (collected[W] == false && G->dist[V][W] < MAX_DIST)
            {
                if (G->dist[V][W] < 0) /* 若有负边 */
                    return;            /* 不能正确解决，返回错误标记 */
                /* 若收录V使得dist[W]变小 */
                if (dist[V] + G->dist[V][W] < dist[W])
                {
                    dist[W] = dist[V] + G->dist[V][W]; /* 更新dist[W] */
                    cost[W] = cost[V] + G->cost[V][W];
                }
                else if (dist[V] + G->dist[V][W] == dist[W] &&
                         cost[V] + G->cost[V][W] < cost[W])
                {
                    cost[W] = cost[V] + G->cost[V][W];
                }
            }
    } /* while结束*/

    FreeHeap(H);
    free(G);
}

bool isEmpty(MinHeap H)
{
    return H->Size == 0;
}

bool isFull(MinHeap H)
{
    return H->Size == H->Capacity;
}

ELEMENT_TYPE DelMin(MinHeap H, int dist[])
{
    if (!isEmpty(H))
    {
        ELEMENT_TYPE min, last;
        int parent, child;

        min = H->Elements[1];
        last = H->Elements[H->Size--];

        for (parent = 1; 2 * parent <= H->Size; parent = child)
        {
            child = 2 * parent;
            if ((child != H->Size) && (dist[H->Elements[child]] > dist[H->Elements[child + 1]]))
            {
                child++;
            }
            if (dist[last] <= dist[H->Elements[child]])
            {
                break;
            }
            else
            {
                H->Elements[parent] = H->Elements[child];
            }
        }

        H->Elements[parent] = last;

        return min;
    }
    else
    {
        return ERROR;
    }
}

void PercUp(MinHeap H, int p, int dist[])
{ /*根据顶点的dist值，决定顶点在堆中的存储位置。
  对dist[H->Elements[child]] > dist[H->Elements[child + 1]]的理解
  dist[x] > dist[y],本质是比较两个顶点之间的dist值，x,y是顶点序号。
  dist[x]的初始值通过dist[V] = G->dist[S][V]获得，并用dist[W] = dist[V] + G->dist[V][W]更新
  child是顶点在堆中的索引，H->Elements[child]存储的是顶点序号
  所以dist[H->Elements[child]]是顶点的dist值。
  */

    int parent, child;
    ELEMENT_TYPE X;
    X = H->Elements[p];

    for (parent = p; 2 * parent <= H->Size; parent = child)
    {
        child = 2 * parent;
        if ((child != H->Size) && (dist[H->Elements[child]] > dist[H->Elements[child + 1]]))
        {
            child++;
        }
        if (dist[X] <= dist[H->Elements[child]])
        {
            break;
        }
        else
        {
            H->Elements[parent] = H->Elements[child];
        }
    }

    H->Elements[parent] = X;
}

void FreeHeap(MinHeap H)
{
    if (H != NULL)
    {
        free(H->Elements);
        free(H);
    }
}

MinHeap CreateHeap(int MaxSize)
{
    MinHeap H = (MinHeap)malloc(sizeof(struct _MinHeap));
    H->Elements = (ELEMENT_TYPE *)malloc((MaxSize + 1) * sizeof(ELEMENT_TYPE));
    H->Elements[0] = MIN_DATA;
    H->Size = 0;
    H->Capacity = MaxSize;

    return H;
}

void BuildMinHeap(MinHeap H, int dist[])
{ // p表示顶点在堆中的位置
    int p;
    for (p = H->Size / 2; p > 0; p--)
    {
        PercUp(H, p, dist);
    }
}
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311

小结：
本题的最小堆比用循环的方式实现FindMinDist要难一些，主要是要理解和修改堆的几个实现，核心是构造和维护最小堆要根据dist的值，来维护对应的顶点。