最短路算法

最短路求源点到其他点或任意两点的最小路径权。算法选择取决于边权是否非负、是否有负环以及图的规模。

Dijkstra：非负边

维护当前最短的未确定点，每次从小根堆取距离最小的点并松弛其出边。非负权保证该点距离已最终确定。

priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>> pq;
pq.push({0,s});
while(!pq.empty()){auto [d,u]=pq.top();pq.pop(); if(d!=dist[u]) continue;
 for(auto [v,w]:g[u]) if(dist[v]>d+w)
   dist[v]=d+w,pq.push({dist[v],v});
}

其他算法

• BFS：边权全为 1 的单源最短路，O(n+m)。
• Bellman-Ford：可处理负边，连续第 n 次仍可松弛说明存在从源可达的负环，O(nm)。
• SPFA：队列式松弛，实践可能快但最坏 O(nm)，不可作为稳定复杂度保证。
• Floyd：dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])，全源 O(n³)。

初始化 dist[s]=0、其余为 INF；松弛前确保前项不是 INF。若需还原路径，记录每次更新的前驱。整理自 XOJ《最短路算法》。