1、Dijkstra算法
不能处理边权为负的情况,复杂度O(nlogn)
步骤与基本思路
(1)初始化距离数组dist[N],将其所有值赋为0x3f,并将起点1的dist初始化为0,存入优先队列heap中
(2)从所有未被遍历的点中找到与起点1的距离dist[i]最小的点,并将该点标记为已遍历
(3)利用刚刚遍历的这个点 i 更新所有 i 的出边所连的点与起点1的距离,更新后存入heap中
(4)重复操作(2)(3)直至heap空
Dijkstra板子
int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1});
while (heap.size()) { auto t = heap.top(); heap.pop();
int distance = t.first, ver = t.second;
if (st[ver]) continue; st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[ver] + w[i]) { dist[j] = dist[ver] + w[i]; heap.push({dist[j], j}); } } }
if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; }
|
2、Bellman-Ford算法
可以解决对边数有要求的最短路问题,复杂度O(n^2)
步骤与基本思路
(1)初始化距离数组dist[N],将其所有值赋为0x3f,并将起点1的dist初始化为0
(2)遍历 k 次,第 i 次表示这一轮的最短路最多经过 i 条边:每轮先复制上一轮的dist(防止本轮前面的dist更新对后面的更新有影响),然后遍历所有边,更新dist为最小值
Bellman-Ford板子
struct Edge { int a, b, w; }edges[M];
void bellman_ford() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < k; i ++ ) { memcpy(last, dist, sizeof dist); for (int j = 0; j < m; j ++ ) { auto e = edges[j]; dist[e.b] = min(dist[e.b], last[e.a] + e.w); } } }
|
3、SPFA算法
可以解决有负权边的情况,还可以判断负环,复杂度O(n^2)
步骤与基本思路
(1)初始化距离数组dist[N],将其所有值赋为0x3f,并将起点1的dist初始化为0
(2)建立队列q,将起点1存入队列中。同时建立st数组记录哪些点入队
(3)每轮取出队头,遍历与队头相连的所有点,更新这些点的dist,并将不在队中的点入队
(4)重复(3),直到队空
SPFA板子
int spfa() { memset(dist, 0x3f, sizeof dist); dist[1] = 0;
queue<int> q; q.push(1); st[1] = true;
while (q.size()) { int t = q.front(); q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) { q.push(j); st[j] = true; } } } } return dist[n]; }
|
4、Floyd算法
数据范围小时用该方法合适,可以处理负权边,时间复杂度O(n^3)
步骤与基本思路
设置 k 为中转站,每轮更新 i -> j 距离为 i -> j 和 i -> k k -> j 的最小值
Floyd板子
void floyd() { for (int k = 1; k <= n; k ++ ) { for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= n; j ++ ) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } }
|