一、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]
小栗子
#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"); }
注意:
不能将最外层的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] } } }
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;//返回最小生成树的边权之和 }
2)小试牛刀
题目:
一个无向图,顶点为N个,其中M条边已给定,现在要从K条备选边中选出若干条,使得整个图连通,且选出的边权值和最小。
4 4
1 2 2
1 4 1
2 3 3
3 4 4
第一行的两个数据分别为N顶点个数和边M的个数;下面的M行为每条边的数据,
起始点和终点,还有每条边的权值。本数据使整个图连通的最小权值之和为6.