一、Floyd算法

解决全源最短路径问题——求任意两点u、v之间的最短路径长度，dis[i][j]表示从顶点i到顶点j的最短距离，伪代码如下：

枚举顶点k
	以顶点k作为中介点，枚举所有顶点对i和j
		如果dis[i][k]+dis[k][j]<dis[i][j]成立
			赋值dis[i][j]=dis[i][k]+dis[k][j]

  

 

  
1
  
2
  
3
  
4
 

小栗子

#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=1000000000;
const int MAXV=200;
int n,m;//n为顶点数，m为边数
int dis[MAXV][MAXV];//dis[i][j]为顶点i和j的最短距离

void Floyd(){
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j]){
					dis[i][j]=dis[i][k]+dis[k][j];//找到更短的路径
				}
			}
		}
	}
}
int main(){
	int u,v,w;
	fill(dis[0],dis[0]+MAXV*MAXV,INF);//dis数组赋初值
	scanf("%d%d",&n,&m);//顶点数n，边数m
	for(int i=0;i<n;i++){
		dis[i][i]=0;//顶点i到顶点i的距离初始化为0
	}
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&u,&v,&w);
		dis[u][v]=w;//u点指向v点的边权为w
	}
	Floyd();
	for(int i=0;i<n;i++){//输出dis数组
		for(int j=0;j<n;j++){
			printf("%d ",dis[i][j]);
		}
		printf("\n");
	}
	//return 0;
	system("pause");
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
 

注意：
不能将最外层的k循环放到内层（即产生i->j->k的三重循环），否则如果当较后访问的dis[u][v]能优化后，之前访问的dis[i][j]会因为已经被访问而无法获得进一步优化（这里i、j先于u、v进行访问）。

二、Prim算法

（1）模板

求最小生成树，

基本思想

——对图设置集合S（存放已经被访问的顶点），然后执行n次下面的2个步骤（n个顶点）：
1）每次从集合V-S中选择与集合S最近的一个顶点（记作u），访问u并将其加入集合S，同时把这条离集合S最近的边加入最小生成树中。
2）令u点作为集合S与集合V-S连接的接口，优化从u能到达的未访问顶点v与集合S的最短距离。
解决最小生成树问题。

//G为图，一般设为全局变量，数组d为顶点与集合S的最短距离
Prim(G,d[]){
	初始化;
	for(循环n次){
		u=使d[u]最小的还未被访问的顶点的标号
		记u已被访问;
		for(从u出发能到达的所有顶点v){
			if(v未被访问&&以u为中介点使得v与集合S的最短距离d[v]更优){
				将G[u][v]赋值给v与集合S的最短距离d[v]
			}
		}
	}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

Prim和Dijkstra算法思路类似，只有d[]含义不同——前者d[]指顶点Vi与集合S的最短距离， 后者的d[]指起点s到达顶点Vi的最短距离；区别在于最短距离是顶点Vi针对“起点s”还是“集合S”。

具体实现（邻接矩阵版本）

const int MAXV=1000;//最大顶点数
const int INF=1000000000;//设INF为一个很大的数

int n,G[MAXV][MAXV];//n为顶点数，MAXV为最大顶点数
int d[MAXC];//顶点与集合S的最短距离
bool vis[MAXV]={false};//访问数组

int prim(){//默认0号为初始点，函数返回最小生成树的边权之和
	fill(d,d+MAXV,INF);
	d[0]=0;//只有0号顶点到集合S的距离为0，其余为INF
	int ans=0;//存放最小生成树的边权之和
	for(int i=0;i<n;i++){
		int u=-1,MIN=INF;//u使d[u]最小，MIN存放该最小的d[u]
		for(int j=0;j<n;j++){//找到未访问的顶点中d[]最小的
			if(vis[j]==false&&d[j]<MIN){
				u=j;
				MIN=d[j];
			}
		}
		//找不到小于INF的d[u],则剩下的顶点和集合S不连通
		if(u==-1) 
			return -1;
		vis[u]=true;
		ans+=d[u];//将与集合S距离最小的边加入最小生成树
		for(int v=0;v<n;v++){
			//v未访问&&u能到达v&&以u为中介点可以使v离集合S更近
			if(vis[v]==false&&G[u][v]!=INF&&G[u][v]<d[v]){
				d[v]=G[u][v];
			}
		}
	}
	return ans;//返回最小生成树的边权之和
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
 

（2）小试牛刀

题目：
一个无向图，顶点为N个，其中M条边已给定，现在要从K条备选边中选出若干条，使得整个图连通，且选出的边权值和最小。
4 4
1 2 2
1 4 1
2 3 3
3 4 4
第一行的两个数据分别为N顶点个数和边M的个数；下面的M行为每条边的数据，
起始点和终点，还有每条边的权值。本数据使整个图连通的最小权值之和为6.

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/112914757