最短路径算法

article/2025/8/25 5:40:47

1.最短路径算法分为单源最短路径算法和多源最短路径算法

（a）单源最短路径算法，可以计算出从起点到任意一个起点的最短路径。

例如：Dijkstra算法，SPFA算法

（b）多源最短路径算法，可以计算出任意两点之间的最短路径。

例如：Floyd算法。

（c）负权边，就是指图中有边的权值为负数，此时Dijkstra算法失效（无法计算出最短路径），SPFA算法和Floyd算法仍然有效。

（d）负权回路，也叫负权环。所有最短路径算法全部失效，但是用SPFA算法可以检测出负权环，Dijkstra算法，Floyd算法无法检测出负权环。

2.Dijkstra算法和SPFA算法

（1）Dijkstra算法分三步：第一步选最小，第二步标记，第三步更新。

（2）SPFA算法，本质上是BFS算法，主要采用队列，其关键操作是出队和入队。

（a）出队：每次队首的父结点出队

（b）入队：初始时起点入队，之后孩子入队必须要满足两个条件：条件1--经过父结点能使该孩子到起点的距离更短，条件2--孩子未在队中

代码示例：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2500+10,maxm=6200+10;//边数和点数要开足够
const int INF=1<<30;//2的30次方
struct Edge
{int v;int w;int next;
}e[maxm*2];
int cnt;//边的编号
int head[maxn];
int n, m, s, t;inline void AddEdge(int u,int v,int w)
{cnt++;//边的编号增加1e[cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;
}//SPFA 最环0（nm）随机图实践性很好。
void SPFA()
{int inq[maxn],d[maxn];queue<int> q;memset(inq,0,sizeof(inq));for(int i=1;i<=n;i++){d[i]=INF;}d[s]=0;//设置起点距离为零q.push(s);//起点入队inq[s]=1;//标记起点已经入队while(!q.empty()){int u=q.front();//取出父结点//cout<<u<<endl;q.pop();//父亲出队inq[u]=0;//表示是否在队里边，0表示不在队里，1表示在队里for(int i=head[u];i>=0;i=e[i].next){int v=e[i].v,w=e[i].w;if(d[v]>d[u]+w)//如果经过父亲结点u到子结点v的路径长度，比原先v到起点的路径更短{d[v]=d[u]+w;if(!inq[v])//如果v不在队列里，就让v入队{q.push(v);//让v入队，v已入队inq[v]=1;//标记//cout<<v<<":"<<d[v]<<" ";}}}}printf("%d\n",d[t]);
}//Dijkstra 0(mlogn)
struct HeapNode
{
//小根堆，储存最小的int u;//结点编号int d;//表示结点到起点的最短路径长度bool operator<(const HeapNode& rhs) const{return d>rhs.d;//定义了堆的排序规则}
};void Dijstra()//使用优先队列算法优化的算法
{int d[maxn];//它存第i个点到终点的最短路径priority_queue<HeapNode> q;for(int i=1;i<=n;i++){d[i]=INF;//先初始化让所有点到起点的距离为无穷大}d[s]=0;//将起点到起点的距离为零q.push((HeapNode){s,d[s]});//找到dist最小的（强制类型转换）while(!q.empty()){HeapNode x=q.top();//取出队首父亲xq.pop();//父亲出队int u=x.u;//取出x点的结点编号if(x.d != d[u]){continue;//跳过本次循环}for(int i=head[u];i>=0;i=e[i].next){int v=e[i].v;//取出第i条边的终点int w=e[i].w;//取出第i条边的权值if(d[u]+w<d[v])//如果经过父亲结点u到子结点v的路径长度，比原先v到起点的路径更短{d[v]=d[u]+w;//更新孩子q.push((HeapNode){v,d[v]});//被更新的子结点入队}}}cout<<d[t];//输出从t点到起点最短路径的长度
}
int main()
{memset(head,-1,sizeof(head));//初始化链表头cin>>n>>m>>s>>t;//读取结点数，边数，起点，终点int u, v, w;//边的起点，终点，权值for(int i=1;i<=m;i++)//读取边并存成图{cin>>u>>v>>w;AddEdge(u,v,w);AddEdge(v,u,w);}//Dijstra();SPFA();return 0;
}
/*
6
9
1 4
1 2 1
1 6 2
2 3 4
2 6 4
3 4 2
3 6 1
4 5 3
4 6 3
5 6 5
*/

调试技巧：用队列的算法在调试时通常通过父亲和孩子来找问题，一定要验证输入的正确性，（通过输出来验证）

3.Floyd算法

（1）这个算法是最简单功能最强大的最短路径算法，但缺点是时间复杂度高。

（2）相比其他算法，此算法必须背过。

（3）此算法是插点法，即如果经过k点能使i点和j点的最短路径变短，那就经过k点。此算法使用枚举方法，依次插入一个点，更新任意两点之间的最短路径。即在任意两点之间插入1号点，看是否能够跟新其最短路径；在任意两点之间插入2号点，看是否能够跟新其最短路径；...在任意两点之间插入n号点，看是否能够跟新其最短路径。

（4）关键代码：

（5）注意事项：中间点k必须为外层循环（不可以互换)，起点i和终点j可以互换。

（6）示例代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
const int INF=10000;
int n;//点的数量
int m;//边的数量
int g[maxn][maxn];//二维数组存图,邻接矩阵存图,数组的初始值全部为0
int d[maxn][maxn];//存储任意两点的最短路径长度
void insertEdge(int from,int to,int w)//边的起点终点和权值
{g[from][to]=w;
}
void Floyd()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(d[i][j]>d[i][k]+d[k][j]){d[i][j]=d[i][k]+d[k][j];}}}}
}
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){int from,to,w;cin>>from>>to>>w;insertEdge(from,to,w);insertEdge(to,from,w);}//初始化d数组，若两点之间存有边初始化成权值大小，没有边则初始为无穷大for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(g[i][j]>0)//i到j之间有边{d[i][j]=g[i][j];}else{d[i][j]=INF;}if(i==j){d[i][j]=0;}}}Floyd();for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<i<<"->"<<j<<":"<<d[i][j]<<endl;}}return 0;
}
/*
6
9
1 2 1
1 6 2
2 3 4
2 6 4
3 4 2
3 6 1
4 5 3
4 6 3
5 6 5
*/