- gf25030 的博客
最短路径问题（针对图，半开发状态）
-
gf25030
LV 6
@
2026-5-24 19:45:57
1.floyd算法
Floyd算法是一个优雅而强大的算法，它展示了动态规划思想的简洁美。虽然O(n³)的时间复杂度限制了它在超大规模图上的应用，但在节点数适中的情况下，它依然是最简单易用的所有点对最短路径求解方案。
作为计算机科学学习者，掌握Floyd算法不仅能帮助你解决实际问题，更能加深对动态规划和图论的理解。当你面对一个中等规模的图，需要快速得到所有点对最短路径时，不妨试试这个只有10行代码却蕴含深邃思想的算法。
数据类型的选择：
小规模（n ≤ 200）：使用vector<vector>
大规模（n ≤ 500）：使用静态二维数组
超大规模：考虑其他算法
INF的选择：
使用INT_MAX/2避免加法溢出
或使用0x3f3f3f3f（约10^9）
性能优化：
循环顺序固定为k, i, j
使用局部变量缓存
提前跳过无效状态
适用场景：
节点数 ≤ 500的稠密图
需要所有点对最短路径
状态转移方程（基本在所有floyd题目适用）：dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j]);
例题：USACO08OPEN：Clear And Present Danger S
题解（最优解）
#include<bits/stdc++.h>
using namespace std;
long long ans,n,m,a[10005],f[105][105][105];
int main() {
cin>>n>>m;
for(int i=1; i<=m; i++)cin>>a[i];
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)cin>>f[0][i][j];//可以省下一个danger数组
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j]);
for(int i=1; i<m; i++)ans+=f[n][a[i]][a[i+1]];
cout<<ans;
}
2.dijkstra算法
Dijkstra算法的核心原理可以概括为：
贪心策略：从起点开始，每次选择距离起点最近且未处理的节点，然后尝试通过它更新邻居节点的距离。
三个关键步骤：
- 选最小：从未处理节点中选出距离最小的节点u
- 确定它：u的最短距离已经找到（因为不可能有更短路径）
- 松弛：用u去更新所有邻居的距离
dist[v] = min(dist[v], dist[u] + w)
为什么有效：由于边权非负，当前距离最小的节点不可能通过其他节点绕出更短路，因此可以“确定”下来。
限制：不能处理负权边。
题解
#include<bits/stdc++.h>
using namespace std;
long long n,m,s,dis[200005];
vector<pair<long long,long long> >node[200005];
priority_queue<pair<long long,long long> >q;
bool vis[200005];
void dijkstra(int s){
for(int i=1;i<=n;i++)dis[i]=LONG_LONG_MAX;
dis[s]=0;q.push({0,s});
while(!q.empty()){
int u=q.top().second;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto j:node[u]){
int v=j.first,w=j.second;
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
q.push({-dis[v],v});
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
node[u].push_back({v,w});
}
dijkstra(s);
for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
}