时间复杂度对比#xff1a;

创建图#xff08;CreateGraph#xff09;#xff1a;时…题目

题目和浙大陈越何钦铭数据结构07-图6

旅游规划是一样的不同的是用最小堆实现函数【FindMinDist】。

时间复杂度对比

创建图CreateGraph时间复杂度为O(N^2)因为需要使用两层循环初始化邻接矩阵。

插入边InsertEdge时间复杂度为O(1)因为只是将边的距离和代价插入到邻接矩阵中。

构建图BuildGraph时间复杂度为O(E)其中E为边的个数。

需要进行E次的边的插入操作。

查找未被收录顶点中dist最小者FindMinDist时间复杂度为O(N)需要遍历所有未收录的顶点查找其中dist最小的顶点。

Dijkstra算法主循环时间复杂度为O(N^2)每次循环都需要找到未收录顶点中dist最小的顶点并更新其周围顶点的dist和cost值。

堆实现代码

查找未被收录顶点中dist最小者FindMinDist使用最小堆实现后每次查找最小值的时间复杂度为

O(logN)总共需要进行

Dijkstra算法主循环在每个节点更新最短路径时需要将其邻接节点的信息插入最小堆中插入一个节点的时间复杂度为

O(logN)总共需要插入

O(ElogN)。

同时在每个节点更新最短路径时还需要进行一次堆操作将堆中的最小值取出时间复杂度为

O(logN)总共需要进行

dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int

cost[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef

对于全局的int数组自动初始化为0bool数组初始化为false

int

dist和cost分别保存的是源点到顶点V的距离和开销dist[V]

G-dist[S][V];cost[V]

H-Elements保存的是未收集顶点的编号本例依次是1,2,3H-Elements[H-Size]

V;}}BuildMinHeap(H,

dist[H-Elements[child]]){break;}else{H-Elements[parent]

H-Elements[child];}}H-Elements[parent]

last;return

/*根据顶点的dist值决定顶点在堆中的存储位置。

对dist[H-Elements[child]]

dist[y],本质是比较两个顶点之间的dist值x,y是顶点序号。

dist[x]的初始值通过dist[V]

dist[V]

G-dist[V][W]更新child是顶点在堆中的索引H-Elements[child]存储的是顶点序号所以dist[H-Elements[child]]是顶点的dist值。

*/int

parent,

dist[H-Elements[child]]){break;}else{H-Elements[parent]

H-Elements[child];}}H-Elements[parent]

}void

NULL){free(H-Elements);free(H);}

}MinHeap

sizeof(ELEMENT_TYPE));H-Elements[0]

MIN_DATA;H-Size

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