最小生成树Prim算法和单源最短路径Dijkstra算法
最小生成树Prim算法和单源最短路径Dijkstra算法
问题：
1. （最小生成树）给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，即求最小生成树。
2. （单源最短路径）给定一个权值都为正数的无向连通图和一个源点，确定它到其它点的最短距离。
之所以将这两个问题放在一起，是因为Prim算法与Dijkstra算法的思路和程序都非常相似，都是有贪心策略。
1.解法（Prim算法）：
思路：设连通网络N = { V, E }，U表示已加入到生成树的顶点集合。在初始化阶段，任取一个顶点，用其关联边的权值作为初始的V-U顶点集合的数据。在每一步中，先在V-U顶点集合中选择距离U中任意点“最近”的顶点v，再把v加入到U中，最后看看在新的V-U顶点集合中，是否有哪个顶点距离v比距离U中其它点更近，若有则更新V-U顶点集合中的数据。U的元素个数为V-1，所以共要进行V-1步。
总的时间复杂度为Time =
O(V)*T_EXTRACT-MIN+O(E)*T_DECREASE-KEY
若用数组作为顶点权值的数据结构，T_EXTRACT-MIN用时O(V)，
T_DECREASE-KEY用时O(1)，总共用时O(V^2)
若用最小堆作为顶点权值的数据结构，T_EXTRACT-MIN用时O(lgV)，T_DECREASE-KEY用时O(lgV)，总共用时O((V+E)*lgV)
若用斐波那契堆作为顶点权值的数据结构，T_EXTRACT-MIN平均用时O(lgV)，T_DECREASE-KEY平均用时O(1)，总共用时O(E+V*lgV)
下面的代码使用数组作为顶点权值的数据结构：
[cpp]view plaincopy
1.#include
2.#include
https://www.wendangku.net/doc/ba10710536.html,ing namespace std;
4.
5.#define MAXN 1001
6.#define INF 1000000
7.
8.int lowcost[MAXN]; // 距离U中顶点的最小权值
9.bool visited[MAXN]; // 若为true表示已加入到集合U中
10.int mst[MAXN]; // 距离U中哪个顶点最短
11.int graph[MAXN][MAXN]; // 用矩阵表示图上各边权值
12.
13.void Prim(int n)
14.{
15.int i, j;
16. memset(visited, 0, n*sizeof(bool));
17. visited[0] = true;
18. mst[0] = -1;
19.for (i=1; i 20. { 21. lowcost[i] = graph[0][i]; 22. mst[i] = 0; 23. } 24.for (i=1; i<=n-1; i++) 25. { 26.// 取V-U中的最小权值T_EXTRACT-MIN O(V) 27.int min=INF, minid; 28.for (j=1; j 29.// 用visited数组确定V-U 30.if (!visited[j] && lowcost[j] < min) 31. { 32. min = lowcost[j]; 33. minid = j; 34. } 35. visited[minid] = true; 36.// 减小V-U中的权值T_DECREASE-KEY O(1) 37.for (j=1; j 38.if (!visited[j] && lowcost[j] > graph[minid][j]) 39. { 40. lowcost[j] = graph[minid][j]; 41. mst[j] = minid; 42. } 43. } 44.} 45. 46.int main() 47.{ 48.int n, m, i, j; 49. cin >> n >> m; 50.for (i=0; i 51.for (j=0; j 52. graph[i][j] = INF; 53.for (i=0; i 54. { 55.char a[3], b[3]; 56.int c; 57. scanf("%s %s %d",&a, &b, &c); 58. graph[a[0]-'A'][b[0]-'A'] = c; 59. graph[b[0]-'A'][a[0]-'A'] = c; 60. } 61. Prim(n); 62.int total = 0; 63.for (i=1; i 64. { 65. total += lowcost[i]; 66. printf("%c-%c: %d\n", i+'A', mst[i]+'A', lowcost[i]); 67. } 68. printf("%d\n", total); 69.} 2.解法（Dijkstra算法）： 思路：设连通网络N = { V, E }和给定源点u，U表示已确定最短路径的顶点集合。在初始化阶段，用顶点u所关联边的权值作为初始的V-U 顶点集合的数据。在每一步中，先在V-U顶点集合中选择距离源点u“最近”的顶点v，再把v加入到U中，最后看看在新的V-U顶点集合中，是否有哪个顶点通过顶点v到达源点u比通过U中其它点到达距离更短，若有则更新V-U顶点集合中的数据。U的元素个数为V-1，所以共要进行V-1步。 总的时间复杂度为Time = O(V)*T_EXTRACT-MIN+O(E)*T_DECREASE-KEY 若用数组作为顶点权值的数据结构，T_EXTRACT-MIN用时O(V)， T_DECREASE-KEY用时O(1)，总共用时O(V^2) 若用最小堆作为顶点权值的数据结构，T_EXTRACT-MIN用时O(lgV)，T_DECREASE-KEY用时O(lgV)，总共用时O((V+E)*lgV) 若用斐波那契堆作为顶点权值的数据结构，T_EXTRACT-MIN平均用时O(lgV)，T_DECREASE-KEY平均用时O(1)，总共用时O(E+V*lgV) 下面的代码使用数组作为顶点权值的数据结构： [cpp]view plaincopy 1.#include 2.#include 3. https://www.wendangku.net/doc/ba10710536.html,ing namespace std; 5. 6.#define MAXN 1001 7.#define INF 1000000 8. 9.int lowcost[MAXN]; // 距离源点u的最短距离 10.bool visited[MAXN]; // 若为true表示已加入到集合U中 11.int minroad[MAXN]; // 在最短路径上顶点所连接的前一个顶点 12.int graph[MAXN][MAXN]; // 用矩阵表示图上各边权值 13. 14.void Dijkstra(int n) 15.{ 16.int i, j; 17. memset(visited, 0, n*sizeof(bool)); 18. visited[0] = true; 19. minroad[0] = -1; 20.for (i=1; i 21. { 22. lowcost[i] = graph[0][i]; 23. minroad[i] = 0; 24. } 25.for (i=1; i<=n-1; i++) 26. { 27.// 取V-U中的最小权值T_EXTRACT-MIN O(V) 28.int min=INF, minid; 29.for (j=1; j 30.// 用visited数组确定V-U 31.if (!visited[j] && lowcost[j] < min) 32. { 33. min = lowcost[j]; 34. minid = j; 35. } 36. visited[minid] = true; 37.// 减小V-U中的权值T_DECREASE-KEY O(1) 38.for (j=1; j 39.if (!visited[j] && lowcost[j] > lowcost[minid]+graph[minid][j]) 40. { 41. lowcost[j] = lowcost[minid]+graph[minid][j]; 42. minroad[j] = minid; 43. } 44. } 45.} 46. 47.int main() 48.{ 49.int n, m, i, j; 50. cin >> n >> m; 51.for (i=0; i 52.for (j=0; j 53. graph[i][j] = INF; 54.for (i=0; i 55. { 56.char a[3], b[3]; 57.int c; 58. scanf("%s %s %d",&a, &b, &c); 59. graph[a[0]-'A'][b[0]-'A'] = c; 60. graph[b[0]-'A'][a[0]-'A'] = c; 61. } 62. Dijkstra(n); 63.int total = 0; 64.for (i=1; i 65. { 66. total += lowcost[i]; 67. printf("%c-%c: %d\n", i+'A', minroad[i]+'A', lowcost[i]); 68. } 69. printf("%d\n", total); 70.} 大家有没有觉得两个问题很像啊？哈哈~~