道家人 发表于 2025-4-17 14:32:57

NO.94十六届蓝桥杯备战|图论根本-单源最短路|常规dijkstra|堆优化dijkstra|bellman-ford|spfa(C++)

在图G中，假设                                             v                            i                                       v_{i}                  vi​和                                             v                            j                                       v_{j}                  vj​为图中的两个极点，那么                                             v                            i                                       v_{i}                  vi​到                                             v                            j                                       v_{j}                  vj​路径上所颠末边的权值之和就称为带权路径⻓度。
由于                                             v                            i                                       v_{i}                  vi​到                                             v                            j                                       v_{j}                  vj​的路径可能有多条，将带权路径⻓度最短的那条路径称为最短路径。
最短路⼀般分为两类：


[*]单源最短路，即图中⼀个极点到其它各极点的最短路径。
[*]多源最短路，即图中每对极点间的最短路径
https://i-blog.csdnimg.cn/direct/d49a3fe575534780bca1020130f3701f.png
常规版dijkstra算法

Dijkstra算法是基于贪⼼思想的单源最短路算法，求解的是"⾮负权图"上单源最短路径
https://i-blog.csdnimg.cn/direct/e02b0f31bfbe4484942f9b63db664bb0.png
常规版dijkstra算法流程：


[*]准备⼯作：

[*]创建⼀个⻓度为 n 的 dist 数组，此中 dist 表⽰从出发点到 i 结点的最短路；
[*]创建⼀个⻓度为 n 的 bool 数组 st ，此中 st 表⽰ i 点是否已经确定了最短路。

[*]初始化： dist = 0 ，其余结点的 dist 值为⽆穷⼤，表⽰还没有找到最短路。
[*]重复：在所有没有确定最短路的点中，找出最短路⻓度最⼩的点 u 。打上确定最短路的标记，然后对 u 的出边进⾏松弛操纵；
[*]重复上述操纵，直到所有点的最短路都确定
P3371 【模板】单源最短路径（弱化版） - 洛谷

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1e4 + 10, INF = 2147483647;

int n, m, s;
vector<PII> edges;

LL dist;
bool st;

void dijkstra()
{
    //初始化
    for (int i = 0; i <= n; i++) dist = INF;
    dist = 0;

    for (int i = 1; i < n; i++)
    {
      //找出没有确定最短路的点中，当前最短路最小的点
      int a = 0;
      for (int j = 1; j <= n; j++)
            if (!st && dist < dist)
                a = j;

      //打上标记，松弛
      st = true;

      for (auto& t : edges)
      {
            int b = t.first, c = t.second;
            if (dist + c < dist)
            {
                dist = dist + c;
            }
      }
    }

    for (int i = 1; i <= n; i++) cout << dist << " ";
}

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;
      edges.push_back({v, w});
    }

    dijkstra();

    return 0;
}
堆优化版dijkstra算法

在常规版的根本上，⽤优先级队列去维护待确定最短路的结点。
堆优化版的dijkstra算法流程：


[*]准备⼯作：

[*]创建⼀个⻓度为 n 的 dist 数组，此中 dist 表⽰从出发点到 i 结点的最短路；
[*]创建⼀个⻓度为 n 的 bool 数组 st ，此中 st 表⽰ i 点是否已经确定了最短路；
[*]创建⼀个⼩根堆，维护更新后的结点。（也就是需要确定最短路的结点）

[*]初始化： dist = 0 ，然后将 {0, s} 加到堆⾥；其余结点的 dist 值为⽆穷⼤，表⽰还没有找到最短路。
[*]重复：弹出堆顶元素，假如该元素已经标记过，就跳过；假如没有标记过，打上标记，进⾏松弛操纵。
[*]重复上述操纵，直到堆⾥⾯没有元素为⽌
P4779 【模板】单源最短路径（标准版） - 洛谷

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n, m, s;
vector<PII> edges;

int dist;
bool st;

priority_queue<PII, vector<PII>, greater<PII>> heap;

void dijkstra()
{
    //初始化
    memset(dist, 0x3f, sizeof dist);
    dist = 0;
    heap.push({0, s});

    while (heap.size())
    {
      auto t = heap.top(); heap.pop();

      int a = t.second;
      if (st) continue;
      st = true;
      
      for (auto& x : edges)
      {
            int b = x.first, c = x.second;
            if (dist + c < dist)
            {
                dist = dist + c;
                heap.push({dist, b});
            }
      }
    }
    for (int i = 1; i <= n; i++) cout << dist << " ";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
      int a, b, c; cin >> a >> b >> c;
      edges.push_back({b, c});
    }

    dijkstra();
   
    return 0;
}
bellman-ford算法

Bellman‒Ford算法(之后简称BF算法)是⼀种基于松弛操纵的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进⾏判定。
算法核⼼思想：不断尝试对图上每⼀条边进⾏松弛，直到所有的点都⽆法松弛为⽌
https://i-blog.csdnimg.cn/direct/211aac2972704faabf3ee0f75a627c59.png
Bellman‒Ford算法流程：


[*]准备⼯作：

[*]创建⼀个⻓度为 n 的 dist 数组，此中 dist 表⽰从出发点到 i 结点的最短路。

[*]初始化： dist = 0 ，其余结点的 dist 值为⽆穷⼤，表⽰还没有找到最短路。
[*]重复：每次都对所有的边进⾏⼀次松弛操纵。
[*]重复上述操纵，直到所有边都不需要松弛操纵为⽌
最多重复多少轮松弛操纵？
在最短路存在的情况下，由于⼀次松弛操纵会使最短路的边数⾄少增长1，⽽最短路的边数最多为n-1。因此整个算法最多执⾏轮松弛操纵n-1轮。故总时间复杂度为O(nm)
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1e4 + 10, INF = 2147483647;

int n, m, s;
vector<PII> edges;

LL dist;

void bf()
{
    //初始化
    for (int i = 0; i <= n; i++) dist = INF;
    dist = 0;

    bool flg = false;
    for (int i = 1; i < n; i++)
    {
      flg = false;
      
      for (int u = 1; u <= n; u++)
      {
                        if (dist == INF) continue;

            for (auto& t : edges)
            {
                int v = t.first, w = t.second;
                if (dist + w < dist)
                {
                  dist = dist + w;
                  flg = true;
                }
            }
      }
      if (flg == false) break;
    }
    for (int i = 1; i <= n; i++) cout << dist << " ";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
      int a, b, c; cin >> a >> b >> c;
      edges.push_back({b, c});
    }

    bf();

    return 0;
}
spfa算法

spfa即Shortest Path Faster Algorithm，本质是⽤队列对BF算法做优化。
在BF算法中，很多时候我们并不需要那么多⽆⽤的松弛操纵：


[*]只有上⼀次被松弛的结点，它的出边，才有可能引起下⼀次的松弛操纵；
[*]因此，假如⽤队列来维护"哪些结点可能会引起松弛操纵"，就能只访问必要的边了，时间复杂度就能低落。
spfa算法流程：
[*]准备⼯作：

[*]创建⼀个⻓度为 n 的 dist 数组，此中 dist 表⽰从出发点到 i 结点的最短路；
[*]创建⼀个⻓度为 n 的 bool 数组 st ，此中 st 表⽰ i 点是否已经在队列中。

[*]初始化：标记 dist = 0 ，同时 1 ⼊队；其余结点的 dist 值为⽆穷⼤，表⽰还没有找到最短路。
[*]重复：每次拿出队头元素 u ，去掉在队列中的标记，同时对 u 所有相连的点 v 进⾏松弛操纵。
假如结点 v 被松弛，那就放进队列中。
[*]重复上述操纵，直到队列中没有结点为⽌。
注意注意注意：
固然在⼤多数情况下spfa跑得很快，但其最坏情况下的时间复杂度为O(nm) 。将其卡到这个复杂度也是不难的，所以在没有负权边时最好使⽤Dijkstra算法。
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1e4 + 10, INF = 2147483647;

int n, m, s;
vector<PII> edges;

LL dist;
bool st; //标记哪些节点在队列中

void spfa()
{
    //初始化
    for (int i = 0; i <= n; i++) dist = INF;

    queue<int> q;
    q.push(s);
    dist = 0;
    st = true;

    while (q.size())
    {
      auto a = q.front(); q.pop();
      st = false;

      for (auto& t : edges)
      {
            int b = t.first, c = t.second;

            if (dist + c < dist)
            {
                dist = dist + c;
                if (!st)
                {
                  q.push(b);
                  st = true;
                }
            }
      }
    }
    for (int i = 1; i <= n; i++) cout << dist << " ";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
      int a, b, c; cin >> a >> b >> c;
      edges.push_back({b, c});
    }

    spfa();

    return 0;
}

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页: [1]
查看完整版本: NO.94十六届蓝桥杯备战|图论根本-单源最短路|常规dijkstra|堆优化dijkstra|bellman-ford|spfa(C++)