最小生成树Prim算法和单源最短路径Dijkstra算法

1、最小生成树Prim算法和单源最短路径Dijkstra算法问题：(最小生成树)给定一个带权的无向连通图，如何选取一棵生成树， 使树上所有边上权的总和为最小，即求最小生成树。(单源最短路径)给定一个权值都为正数的无向连通图和一个源点， 确定它到其它点的最短距离。之所以将这两个问题放在一起，是因为Prim算法与Dijkstra算法的思 路和程序都非常相似，都是有贪心策略。1.解法(Prim算法)：思路：设连通网络N = V, E ，U表示已加入到生成树的顶点集合。在初始化阶段，任取一个顶点，用其关联边的权值作为初始的V-U顶点 集合的数据。在每一步中，先在V-U顶点集合中选择距离U中任意点“最 近”

2、的顶点v，再把v加入到。中，最后看看在新的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 用时 0(1)，总共用时 O(VA2)若用最小堆作为顶点权值的数据结构，T_EXTRACT-MIN用时O(lgV),T_DECREASE-KEY 用时 O(lgV)，总共用时 O(V+E)*lgV)若用斐波那契

3、堆作为顶点权值的数据结构，T_EXTRACT-MIN平均用时O(lgV), T_DECREASE-KEY 平均用时 O(1)，总共用时 O(E+V*lgV)下面的代码使用数组作为顶点权值的数据结构：cpp view plaincopy#include #include algorithmusing namespace std;4.#define MAXN 1001#define INF 10000007.int lowcostMAXN; /距离U中顶点的最小权值bool visitedMAXN; /若为true表示巳加入到集合U中int mstMAXN; /距离U中哪个顶点最短int grap

4、hMAXNMAXN; /用矩阵表示图上各边权值12.void Prim(int n)int i, j;memset(visited,0,n*sizeof(bool);visited0 =true;mst0 = -1;for (i=1; in; i+) TOC o 1-5 h z lowcosti = graph0i;msti = 0;for (i=1; i=n-1; i+)/ 取 V-U 中的最小权值T_EXTRACT-MIN O(V)intmin=INF, minid;for (j=1; jn; j+)/用visited数组确定V-Uif (!visitedj & lowcostj min)

5、min = lowcostj;minid = j;34.35.visitedminid = true;36./ 减小 V-U 中的权值 T_DECREASE-KEY O(1)37.for (j=1; j graphminidj)39.40.lowcostj = graphminidj;41.mstj = minid;42.43.44. 45.46. intmain()47. 48.int n, m, i, j;49.cin n m;50.for (i=0; in; i+)51.for (j=0; jn; j+)52.graphij = INF;53.for (i=0; im; i+)54.55

6、.char a3, b3;56.int c;57.scanf(%s %s %d”,&a, &b, &c);58.grapha0-Ab0-A = c;59.graphb0-Aa0-A = c;60.61.Prim(n);62.int total = 0;63.for (i=1; in; i+)64.65.total += lowcosti;66.printf(%c-%c: %dn, i+A, msti+A, lowcosti)67.68.printf(%dn, total);69. 2.解法（Dijkstra 算法）：思路：设连通网络N = V, E 和给定源点u, U表示已确定最短路径的 顶点

7、集合。在初始化阶段，用顶点u所关联边的权值作为初始的V-U顶点集合的数据。在每一步中，先在V-U顶点集合中选择距离源点u“最 近”的顶点v,再把v加入到。中，最后看看在新的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 用时 0(1)，总共用时 O(VA2)若用最小堆作为顶

8、点权值的数据结构，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#include #include algorithm3.using namespace std;5.#define MAXN 1001#define INF 10000008.int lowcostMA

9、XN; /距离源点u的最短距离bool visitedMAXN; /若为true表示巳加入到集合U中int minroadMAXN; /在最短路径上顶点所连接的前一个顶点int graphMAXNMAXN; /用矩阵表示图上各边权值13.void Dijkstra(int n)15. 7.memset(visited, 0, n*sizeof

10、(bool);visited0 = true;minroad0 = -1;for (i=1; in; i+)lowcosti = graph0i;minroadi = 0;for (i=1; i=n-1; i+)/ 取 V-U 中的最小权值 T_EXTRACT-MIN O(V)int min=INF, minid;for (j=1; jn; j+)/用visited数组确定V-Uif (!visitedj & lowcostj min) min = lowcostj;minid = j;visitedminid = true;/ 减小 V-U 中的权值 T_DECREASE-KEY O(1)for (j=1; j lowcostminid+graphminidj)lowcostj = lowcostminid+graphminidj;minroadj = minid;int main()int n, m, i, j;cin n m;for (i=0; in; i+)for (j=0; jn; j+)graphij = INF;for (i=0; im; i+)char a3, b3;int c;58.scanf(%s %s %d”,&a,59.grapha0-Ab060.graphb0-Aa061.62.Dijkstra(n);63.in