目录

1.spfa（Shortest Path Faster Algorithm）：

 2.dijkstra+配对堆优化：

---

 

1.spfa（Shortest Path Faster Algorithm）：

可以处理负边但不能处理负环，时间复杂度为O（kN）k为所有顶点进入队列的平均数，N为顶点个数。

算法思想：源点为s，s到i的当前最短路径为d[i],初始时，s到每个点的d[i]都为无穷大，d[s]为0.算法过程中不断减小d[i]，最终将其中的每个元素减小为实际的最短路。

我们需要维护一个队列，首先将源点入队列，扫描它可以直接走到的节点，对它们进行松弛操作，并且将这些节点入队列，如果已经在队列里了，那就不需要再入队列，我们用一个inq数组来标记某个节点是否在队列里。

 

松弛操作：原理就是“三角形两边之和大于第三边”，判断d[j]>d[i]+w[i,j]，若成立那么将d[j]更新为d[i]+w[i,j]，否则不动。

hdu1874 ac代码：

#include<iostream> #include<cstdio> #include<vector> #include<queue> using namespace std; const int maxn = 205; vector<pair<int, int> >E[maxn]; int n, m; int d[maxn], inq[maxn]; void init() { for (int i = 0;i < maxn;i++)E[i].clear(); for (int i = 0;i < maxn;i++)inq[i] = 0; for (int i = 0;i < maxn;i++)d[i] = 1e9; } int main() { while (cin >> n >> m) { init(); for (int i = 0;i < m;i++) { int x, y, z;scanf("%d%d%d", &x, &y, &z); E[x].push_back(make_pair(y, z)); E[y].push_back(make_pair(x, z)); } int s, t; scanf("%d%d", &s, &t); queue<int>Q; Q.push(s); d[s] = 0;inq[s] = 1; while (!Q.empty()) { int now = Q.front(); Q.pop(); inq[now] = 0; for (int i = 0;i < E[now].size();i++) { int v = E[now][i].first; if (d[v] > d[now] + E[now][i].second) { d[v] = d[now] + E[now][i].second; if (!inq[v]) { inq[v] = 1; Q.push(v); } } } } if (d[t] == 1e9) printf("-1\n"); else printf("%d\n", d[t]); } return 0; }

 2.dijkstra+配对堆优化：

适用于边权为正的图（有向图或无向图） 不适用于处理有负边的图。

算法思想：

1.初始时将源点看成集合s，其他的点为另一个集合，与源点相连的点d[i]为边权值，其他的点为无穷大。

2.取最小的d[i]（这里用到的是优先队列），并将它连着的点加入集合s

3.对与他连着的这个点相邻的节点松弛操作

4.重复2.3直到终点进入集合s

代码如下：

#include<iostream> #include<cstdio> #include<vector> #include<queue> using namespace std; const int maxn = 205; vector<pair<int, int> >E[maxn]; int n, m; int d[maxn]; void init() { for (int i = 0;i < maxn;i++)E[i].clear(); for (int i = 0;i < maxn;i++)d[i] = 1e9; } int main() { while (cin >> n >> m) { init(); for (int i = 0;i < m;i++) { int x, y, z;scanf("%d%d%d", &x, &y, &z); E[x].push_back(make_pair(y, z)); E[y].push_back(make_pair(x, z)); } int s, t; scanf("%d%d", &s, &t); priority_queue<pair<int,int > >Q; d[s] = 0; Q.push(make_pair(-d[s], s)); while (!Q.empty()) { int now = Q.top().second; Q.pop(); for (int i = 0;i < E[now].size();i++) { int v = E[now][i].first; if (d[v] > d[now] + E[now][i].second) { d[v] = d[now] + E[now][i].second; Q.push(make_pair(-d[v],v)); } } } if (d[t] == 1e9) printf("-1\n"); else printf("%d\n", d[t]); } return 0; }