浙大陈越何钦铭数据结构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 <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_VERTEX_NUM 500
#define MAX_DIST 501
#define MAX_COST 501
#define ERROR -1
#define MIN_DATA -1000typedef 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 203 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)
{/* 插入边<V,W> */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,3H->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);}
}

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