最小生成树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)
下面的代码使用数组作为顶点权值的数据结构：
#include <iostream>#include <algorithm>using namespace std;#define MAXN 1001#define INF 1000000int lowcost[MAXN];// 距离源点u的最短距离bool visited[MAXN]; // 若为true表示已加入到集合U中int minroad[MAXN];// 在最短路径上顶点所连接的前一个顶点int graph[MAXN][MAXN];// 用矩阵表示图上各边权值void Dijkstra(int n){int i, j;memset(visited, 0, n*sizeof(bool));visited[0] = true;minroad[0] = -1;for (i=1; i<n; i++){lowcost[i] = graph[0][i];minroad[i] = 0;}for (i=1; i<=n-1; i++){// 取V-U中的最小权值T_EXTRACT-MIN O(V)int min=INF, minid;for (j=1; j<n; j++)// 用visited数组确定V-Uif (!visited[j] && lowcost[j] < min){min = lowcost[j];minid = j;}visited[minid] = true;// 减小V-U中的权值T_DECREASE-KEY O(1)for (j=1; j<n; j++)if (!visited[j] && lowcost[j] > lowcost[minid]+graph[minid][j]){lowcost[j] = lowcost[minid]+graph[minid][j];minroad[j] = minid;}}}int main(){int n, m, i, j;cin >> n >> m;for (i=0; i<n; i++)for (j=0; j<n; j++)graph[i][j] = INF;for (i=0; i<m; i++){char a[3], b[3];int c;scanf("%s %s %d",&a, &b, &c);graph[a[0]-'A'][b[0]-'A'] = c;graph[b[0]-'A'][a[0]-'A'] = c;}Dijkstra(n);int total = 0;for (i=1; i<n; i++){total += lowcost[i];printf("%c-%c: %d\n", i+'A', minroad[i]+'A', lowcost[i]);}printf("%d\n", total);}