首页 > 代码库 > 最短路（转）模板
最短路（转）模板
基本最短路算法集锦
算法总结：
①Dijkstra算法用的是贪心策略，每次都找当前最短路径的下一个最短距离点。所以不适合带有负权的情况。至于时间效率通过各种优化可以到达不同的程度。但是朴素的Dijkstra算法永远是最稳定的。
②Bellman-Ford算法是Dijkstra的一种变式，它摒弃了贪心的策略，但是每次都需要松弛所有的路径，所以也适合负权的情况。但是时间效率较低。有资料显示，Bellman-Ford算法也可以应用贪心策略，这属于高级技巧，这里不予考虑。
③Floyd算法用的是动态规划的思想，由于是不定源点，所以它需要对所有的情况进行松弛操作，最终获得所有的最短路径长度。由于需要遍历，所以它的时间效率比较低。但是遍历策略好的话，还是能很快得到想要的结果。
④SPFA算法是用FIFO队列优化的Bellman-Ford算法，所以支持负权的情况，由于已经将需要考虑的节点放入队列中，所以避免了很多不必要的松弛，时间效率也相对较高。由于队列中无法进行修改，所以时间效率相对不稳定。
⑤所有的队列优化其实都能转化为hash优化，这里不再考虑更进一步的优化。
一、Dijkstra算法：单源到所有节点的最短路算法。
算法要求：可以是无向图或有向图，所有边权均为正，最短路存在。如果图是五环图，则最长路也一定存在，但是如果是有环图，则最长路不一定存在。
算法思想：每次比较所有的从源点可以到达的路的长度，然后选出最短的一条放入源点集合，然后更新最短路径长度。这样，当所有的点都在源点集合中时，得到的长度就是最短路长度。
（1）使用邻接矩阵的稠密图普通Dijkstra算法
算法时间复杂度：O(n^2)
算法代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF (1<<31)-1 //int最大值
#define MAXN 100 //最大节点数
int dist[MAXN],c[MAXN][MAXN];
//dist[i]存放从源点到i节点的最短距离，c数组用来表示图
int n,line; //n为节点数，line为边数
//迪杰斯特拉算法主算法模块
void Dijkstra(int v) //v代表源点
{
inti,j,temp,u; //temp用于暂时存放最短路径长度
boolvis[MAXN]; //判定重复标记数组
for(i=0;i<n;i++) //dist数组与vis数组的初始化
{
dist[i]=c[v][i];
vis[i]=0;
}
dist[v]=0; //源点到源点的距离设为0
vis[v]=1; //源点默认为已经访问
for(i=0;i<n;i++) //总共应该遍历n次
{
temp=INF; //初始化temp为最大值
u=v; //初始化最短节点为当前节点
for(j=0;j<n;j++)if((!vis[j])&&dist[j]<temp)
{
u=j; //找出v距离最短的节点u
temp=dist[j]; //更新最短距离
}
if(temp==INF)return; //不存在其它节点了，返回
vis[u]=1; //标记该最短节点为已经访问
for(j=0;j<n;j++)if((!vis[j])&&dist[u]+c[u][v]<dist[j]) //松弛操作
dist[j]=dist[u]+c[u][v]; //更新最短距离
}
}
int main()
{
int p,q,len,i,j,origin;
while(scanf(“%d%d”,&n,&line))
{
if(!n&&!line) break; //如果图为空白图，则结束
for(i=0;i<n;i++)
for(j=0;j<n;j++)
c[i][j]=INF; //初始化节点间距离，默认为节点间全部不连通
while(line--) //输入这line条边的内容
{
scanf(“%d%d%d”,&p,&q,&len);
//p为边的起点,q为边的终点,len为边的长度
//下面是无向图的输入方式
if(len<c[p][q])
{
c[p][q]=len;
c[q][p]=len;
}
/*下面是有向图的输入方式
if(len<c[p][q])
c[p][q]=lem;
以上是有向图的输入方式*/
}
for(i=0;i<n;i++)
dist[i]=INF; //初始化最短距离数组为最大长度
scanf(“%d”,&origin);
Dijkstra(origin); //最短路算法调用
printf(“%d\n”,dist[n]);
}
}
（2）使用邻接表的稀疏图的普通Dijkstra算法
算法时间复杂度：O(m*log(n))
算法代码：（代码以无向图为例,有向图部分以注释形式写在代码中）
###头文件以及宏定义部分省略###
int first[MAXN]; //first[u]保存节点u的第一条边的编号
int u[MAXN],v[MAXN],w[MAXN];
//u[i]表示第i条边的一端端点，v[i]表示第i条边的另一端端点，w[i]表示第i条边的长度
int next[2*MAXN]; //next[i]表示第i条边的下一条边的编号【无向图】
//int next[MAXN]; next[i]表示第i条边的下一条边的编号。【有向图】
#########省略部分#########
scanf(“%d%d”,&n，&m);
for(i=0;i<n;i++) first[i]=-1; //初始化链表表头
for(i=0;i<2*line;i++) //输入2*line条边，每次将边首插法插入链表表头（避免遍历链表）。
//如果是有向图，那么只有line条边，即i<line。
{
scanf(“%d%d%d”,&u[i],&v[i],&w[i]);
next[i]=first[u[i]];
first[u[i]]=i;
//以下只有无向图才有
i++;
u[i]=v[i-1];
v[i]=u[i-1];
next[i]=first[u[i]];
first[u[i]]=i;
//以上只有无向图才有
}
//对应的Dijkstra算法
void Dijkstra(int x) //v代表源点
{
inti,j,temp,minu; //temp用于暂时存放最短路径长度
boolvis[MAXN]; //判定重复标记数组
for(i=first[x];i!=-1;i=next[i]) //dist数组与vis数组的初始化
{
dist[v[i]]=w[i];
vis[v[i]]=0;
}
dist[x]=0; //源点到源点的距离设为0
vis[x]=1; //源点默认为已经访问
for(i=0;i<n;i++) //总共应该遍历n次
{
temp=INF; //初始化temp为最大值
minu=x; //初始化最短节点为当前节点
for(j=first[x];j!=-1;j=next[j])
{
if((!vis[v[j]])&&dist[v[j]]<temp)
{
minu=j; //找出v距离最短的节点uu
temp=dist[v[j]]; //更新最短距离
}
}
if(temp==INF)return; //不存在其它节点了，返回
vis[minu]=1; //标记该最短节点为已经访问
for(j=first[x];j!=-1;j=next[j])if((!vis[v[j]])&&dist[minu]+w[j]<dist[v[j]]) //松弛操作
dist[v[j]]=dist[minu]+w[j]; //更新最短距离
}
}
（3）使用优先队列的Dijkstra优化算法
算法时间复杂度：O(n*lgn+ m)。一般情况下最快。
算法代码：
#include <queue> //需要优先队列
#include <utility> //需要pair类型
######其他头文件已经宏定义省略######
int first[MAXN]; //first[u]保存节点u的第一条边的编号
int u[MAXN],v[MAXN],w[MAXN];
//u[i]表示第i条边的一端端点，v[i]表示第i条边的另一端端点，w[i]表示第i条边的长度
int next[2*MAXN]; //next[i]表示第i条边的下一条边的编号【无向图】
//int next[MAXN]; next[i]表示第i条边的下一条边的编号。【有向图】
#########省略部分#########
scanf(“%d%d”,&n，&m);
for(i=0;i<n;i++) first[i]=-1; //初始化链表表头
for(i=0;i<2*line;i++) //输入2*line条边，每次将边首插法插入链表表头（避免遍历链表）。
//如果是有向图，那么只有line条边，即i<line。
{
scanf(“%d%d%d”,&u[i],&v[i],&w[i]);
next[i]=first[u[i]];
first[u[i]]=i;
//以下只有无向图才有
i++;
u[i]=v[i-1];
v[i]=u[i-1];
next[i]=first[u[i]];
first[u[i]]=i;
//以上只有无向图才有
}
typedef pair<int,int> pii; //定义双对象类型
priority_queue<pii,vector<pii>,greater<pii>> pq; //声明最小出队的优先队列
//对应的Dijkstra算法
int Dijkstra(int x)
{
inti,j;
pq.push(make_pair(d[x],x);
while(!pq.empty())
{
piiminu=pq.top();pq.pop();
intx=minu.second;
if(minu.first!=dist[x])continue;
for(inti=first[x];i!=-1;i=next[i]) if(d[v[i]]>dist[x]+w[i])
{
dist[v[i]]=dist[x]+w[i];
pq.push(make_pair(d[v[i]],v[i]));
}
}
}
二、Bellman-Ford算法：单源到所有节点的最短最长路算法。
算法要求：可以使无向图或者有向图。边权可以存在负值。当然最短路不一定存在，当最短路存在时，可以求出最短路长度。如果图为有环图，则最短路不一定存在，最长路也不一定存在。如有负权则输出错误提示。也适合求解约束拆分系统的不等式问题。
算法思想：如果最短路存在，一定存在一个不含环的最短路。在边权可正可负的图中，环有零环、正环、负环3种。如果包含零环或正环，去掉以后路径不会变长；如果包含负环，则最短路不存在。可以通过n-1轮松弛操作得到。
（1）朴素的BF算法。
算法时间复杂度：O(mn)
算法代码：
const int N =205;
const int M =20005;
const int MAXN = 1000000000
int dist[N];
//自定义边的结构体
struct edge{int u,v,w;}e[M]; //u,v分别是边的两端点，w为边长度
//初始化dist数组
void init(int vs，int s)
{
inti;
for(i=0;i<vs;i++)
dist[i]=MAXN;
dist[s]=0;
return;
}
//松弛操作，成功返回true，失败返回false
bool relax(int u,int v,int w)
{
if(dist[v]>dist[u]+w)
{
dist[v]=dist[u]+w;
returntrue;
}
return false;
}
//BF主算法模块，返回false表示算法失败，图中存在负环。
bool bellmanFord(int es,int vs,int s) //es表示边数，vs表示点数，s表示起点
{
inti,j;
init(vs,s);
boolflag;
for(i=0;i<vs-1;i++) //应进行vs-1次松弛操作
{
flag=false;
for(j=0;j<es;j++)
if(relax(e[j].u,e[j].v,e[j].w))
flag=true;
return flag;
}
}
int main()
{
intn,m,i;
while(scanf(“%d%d”,&n,&m)!=EOF)
{
for(i=0;i<m;i++)
{
scanf(“%d%d%d”,&e[i].u,&e[i].v,&e[i].w);
e[m+i].u=e[i].v;
e[m+i].v=e[i].u;
e[m+i].w=e[i].w;
}
if(bellmanFord(m<<1,n,1))
printf(“%d\n”,dist[n]);
else printf(“No\n”);
}
return 0;
}
（2）使用FIFO队列的优化BF算法(使用邻接表)
算法时间复杂度：O(mn)
算法代码：
#include <queue>
#define INF (1<<31)-1
######其他头文件以及宏定义省略######
int first[MAXN]; //first[u]保存节点u的第一条边的编号
int u[MAXN],v[MAXN],w[MAXN];
//u[i]表示第i条边的一端端点，v[i]表示第i条边的另一端端点，w[i]表示第i条边的长度
int next[2*MAXN]; //next[i]表示第i条边的下一条边的编号【无向图】
//int next[MAXN]; next[i]表示第i条边的下一条边的编号。【有向图】
#########省略部分#########
queue<int> q;
bool inq[MAXN];
bool bellmanFord(int x)
{
int i,j;
bool ans;
for(i=0;i<n;i++)d[i]=!i?0:INF;
memset(inq,0,sizeof(inq)); //在队列中的标志
q.push(x);
ans=false;
while(!q.empty())
{
int x=q.front();q.pop();
inq[x]=false;
for(i=first[x];i!=-1;i=next[i]) if(dist[v[e]]>dist[x]+w[e])
{
dist[v[e]]=dist[x]+w[e];
ans=true;
if(!inq[v[e]])
{
inq[v[e]]=true;
q.push(v[e]);
}
}
}
return ans;
}
三、Floyd-Warshall算法：任意两点之间的最短路
算法要求：无特殊要求。
算法思想：动态规划。
时间复杂度：O(n^3)
算法代码：
#define MAXN 100
#define INF (1<<31)-1
int n,m,p,q;
int f[MAXN+10][MAXN+10];
void Floyd()
{
inti,j,k;
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(f[i][k]+f[k][j]<f[i][j])
f[i][j]=f[i][k]+f[k][j];
}
}
}
if(f[0][n-1]==INF) printf(“0\n”);
else printf(“%d\n”,f[0][n-1]);
}
int main()
{
inta,b,c,i;
while(~scanf(“%d%d”,&n,&m))
{
if(!n&&!m) break;
for(p=0;p<n;p++)
for(q=0;q<n;q++)
f[p][q]=INF;
for(i=0;i<m;i++)
{
scanf(“%d%d%d”,&a,&b,&c);
f[a][b]=c;
f[b][a]=c;
}
floyd();
}
return 0;
}
四、SPFA算法：单源点最短路的高效实用算法
算法要求：无特殊要求
算法思想：用FIFO队列优化的BF算法。
算法时间复杂度：O(k|E|),k为常数，一般k<=2
算法代码：
#include <queue>
#######省略部分######
#define INF (1<<31)-1
#define N 1010
int dist[N],n,m;
int edge[N][N];
bool vis[N];
void spfa(int s)
{
inti,u;
memset(vis,false,sizeof(vis));
for(i=0;i<n;i++)dist[i]=INF;
queue<int>q;
q.push(s);
vis[s]=true;
dist[s]=0;
while(!q.empty())
{
u=q.front();
q.pop();
vis[u]=false;
for(i=0;i<n;i++)
{
if(dist[i]>dist[u]+edge[u][i])
dist[i]=dist[u]+edge[u][i];
if(!vis[i])
{
vis[i]=true;
q.push(i);
}
}
}
}
int main()
{
inti,j,a,b,c,origin;
while(scanf(“%d%d”,&n,&m)!=EOF&&(n||m))
{
for(i=0;i<N;i++)
for(j=0;j<i;j++)
{
edge[i][j]=INF;
edge[j][i]=INF;
}
},
for(i=0;i<m;i++)
{
scanf(“%d%d%d”,&a,&b,&c);
if(edge[a][b]>c)
{
edge[a][b]=c;
edge[b][a]=c;
}
scanf(“%d”,&origin);
spfa(origin);
printf(“%d\n”,dist[n]);
}
return 0;
}
最短路（转）模板