一、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.
