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}); // first为dist second为具体的点
while (heap.size())
{
auto t = heap.top(); // 即取出与起始距离最短点
heap.pop();
int distance = t.first, ver = t.second;
if (st[ver]) continue;
st[ver] = true;
// 遍历所有与ver相邻的点 更新他们的dist
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); // 将本轮还没有更新的dist值赋给last
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)文章来源:https://www.toymoban.com/news/detail-605299.html
步骤与基本思路
设置 k 为中转站,每轮更新 i -> j 距离为 i -> j 和 i -> k k -> j 的最小值文章来源地址https://www.toymoban.com/news/detail-605299.html
Floyd板子
void floyd()
{
for (int k = 1; k <= n; k ++ ) // 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]);
}
}
}
}
到了这里,关于【图论】最短路算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!