文章目录

最短路问题是图论中一个很重要的问题

在这里插入图片描述

朴素Dijkstra（迪杰斯特拉）算法求最短路

迪杰斯特拉采取的是贪心算法，将所有顶点分为已标记（下图中绿色打钩的）和未标记的两个集合。从起点开始，不断在未标记点中寻找距离起始点路径最短的顶点，并将其标记（一次找一个），直至所有顶点都被标记为止。
注意1：迪杰斯特拉算法不可以处理存在负权边的图。
注意2：迪杰斯特拉算法我们是用邻接矩阵存储图的

在这里插入图片描述
例题：

在这里插入图片描述

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];//邻接矩阵存储图
int dist[N];//记录每一个点到起始点的距离
bool state[N];//记录该点的最短路径是否已经确认

int Dijkstra()
{
    memset(dist, 0x3f, sizeof dist);//把距离都初始化为无限大
    
    dist[1] = 0;//第一个点到自身距离为0
    
    for(int i = 0; i < n; i++)//n个点要迭代n次
    {
        int t = -1;//t表示当前访问的点,之所以设置-1是因为没有负权边
        for(int j = 1; j <= n; j++)//j表示从1号点开始
        {
            //该步骤说明还未确定最短路的点
            if(!state[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        
        state[t] = true;
        
        for(int j = 1; j <= n; j++)//依次更新每个点所到相邻点路径值
        {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;//第n个点路径值为无穷大，说明不存在最小路径
    return dist[n];
}

int main()
{
    cin >> n >> m;
    
    memset(g, 0x3f, sizeof g);//初始化邻接矩阵，把每个点到原点的距离都初始化为∞，即每个点都不是通的
    
    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);//如果有重边，则保留最短的那一条边
    }
    
    cout << Dijkstra() << endl;
    
    return 0;
}

堆优化Dijkstra算法

在朴素的Dijkstra算法中，我们每次都需要用for循环先找到距离最短的点，时间复杂度是O(n^2)；堆优化Dijkstra算法就是在这里进行优化，利用堆（最小堆）可以直接找到距离最短的点；最小堆我们可以手写一个堆，当然我们可以使用优先队列更快的完成；我们要注意堆优化Dijkstra是应用于稀疏图，稀疏图我们采取的是邻接表来存储边的。

在这里插入图片描述

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 150010;

int n, m;
int h[N], e[N], ne[N], idx;//邻接表
int w[N];//权重
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;//优先队列定义小根堆
    //heap中存的是pair，first是距离，second是哪一个点
    heap.push({0, 1});
    
    while(heap.size())
    {
        PII 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] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h, -1, sizeof h);//初始化邻接表
    scanf("%d%d", &n, &m);
    
    for(int i = 0; i < m; i++)//读取边
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);//不需要担心有重边，最后都会放进堆里，但是弹出的都是最小的
    }
    
    cout << dijkstra() << endl;
    
    return 0;
}

在这里插入图片描述

Bellman-Ford算法

在这里插入图片描述

Dijkstra算法是无法处理存在负权边的；处理负权边我们是采取Bellman-Ford算法或者是SPFA，SPFA算法的适用处更广，但是当有边数权限（在多少步下完成）的时候，我们只能适用Bellman-Ford算法，但在其他情况下我们都可以使用SPFA算法；
Bellman-Ford算法基本原理：
连续进行松弛操作，在每次松弛时把每条边都更新一下，若在n-1次（n-1条边有n个点）松弛后还能更新，则说明图中存在负环，不能计算最短路径
Bellman-Ford的算法效率比较低；其基本步骤是：
for n次
for所有边 a，b，w（松弛操作）
dist[b] = min(dist[b], back[a] + w)
其中back数组是上一次迭代后dist数组的备份；因为是每个点同时向外出发，因此要对dist数组进行备份，如果不进行备份，会发生串联效应，影响下一个点
Bellman-Ford算法存边可以随便存，一般使用结构体来存储边
Bellman_Ford算法是遍历边的

在这里插入图片描述

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 10010;

struct Edge
{
    int a;
    int b;
    int w;
}e[M];//把所有边保存起来

int n, m, k;
int dist[N];
int back[N];//备份数组

int Bellman_Ford()
{
    memset(dist, 0x3f, sizeof dist);//初始化
    dist[1] = 0;
    
    for(int i = 0; i < k; i++)//k次循环
    {
        memcpy(back, dist, sizeof dist);
        for(int j = 0; j < m; j++)//遍历所有边
        {
            int a = e[j].a, b = e[j].b, w = e[j].w;
            dist[b] = min(dist[b], back[a] + w);
        }
    }
    
    if(dist[n] > 0x3f3f3f3f / 2) return 0x3f3f3f3f;
    else return dist[n];
}

int main()
{
    cin >> n >> m >> k;
    
    for(int i = 0; i < m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        e[i] = {a, b, w};
    }
    
    int res = Bellman_Ford();
    if(res == 0x3f3f3f3f) puts("impossible");
    else cout << res << endl;
    
    return 0;
}

SPFA算法

SPFA算法就是对Bellman_Ford算法进行优化的；我们上面知道Bellman_Ford算法会遍历每条边，但是有些边遍历是没有意义的，我们只需要遍历那些到源点距离变小的点才能找到最短路径 ；
SPFA中松弛的概念：一个点到另一个点的路径选择有很多，我们要想找到最优路径，我们肯定要找到中间那个点距离源点距离变小的点，那样这两点之间的路径才会变小

在这里插入图片描述

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx, w[N];//邻接表存边
int dist[N];//保存最短路径的值
bool st[N];//标记点是否在队列中

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);//初始化距离
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true;//1入队
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        
        st[t] = false;//t出队了
        
        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])//j不在队列中，入队
                {
                    q.push(j);
                    st[j] = true;//标记一下，j已入队
                }
            }
        }
    }
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);//邻接表初始化
    
    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    int t = spfa();
    if(t == 0x3f3f3f3f) puts("impossible");
    else cout << t << endl;
    
    return 0;
}

SPFA算法求负环

在解决是否存在负权回路的问题上，我们一般采取的算法是SPFA算法；
原理：从1 ~ n 点的距离，最多会有 n-1 条边，如果出现 >= n条边的话，说明出现了负环（抽屉原理）

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], e[N], ne[N], idx, w[N];//邻接表
int dist[N], cnt[N];//cnt数组记录到起点的边数和
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool spfa()
{
    queue<int> q;
    
    for(int i = 1; i <= n; i++)
    {
        st[i] = true;
        q.push(i);
    }
    
    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];
                cnt[j] = cnt[t] + 1;
                
                //如果超过了n+1次，根据抽屉原理，说明经过某个节点两次，说明有负权回路
                if(cnt[j] >= n) return true;
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    
    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    if(spfa()) puts("Yes");
    else puts("No");
    
    return 0;
}

Floyd（弗洛伊德）算法

Floyd算法的本质是动态规划；是解决多源汇最短路径的主要方法
Floyd算法的思想很简单，就是三层循环，

在这里插入图片描述

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;//INF相当于无穷大--0x3f3f3f3f

int n, m, Q;//Q个询问
int d[N][N];//邻接矩阵

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]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &Q);
    //邻接矩阵初始化
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
            
    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }
    
    floyd();
    
    while(Q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        
        int t = d[a][b];
        if(t > INF / 2) puts("impossible");//因为可能存在负权路径
        else cout << t << endl;
    }
    
    return 0;
}
# 算法 # 图论 # 数据结构
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

【免费下载】 index-tts-vllm：高性能文本转语音解决方案

`index-tts-vllm` 是一款开源的文本转语音（TTS）项目，基于 `index-tts` 进行了优化，通过引入 `vllm` 库重新实现了 GPT 模型的推理过程，大幅提升了推理速度和并发处理能力。项目旨在为开发者提供一个高效、稳定、易于集成的 TTS 解决方案。## 项目技术分析`index-tts-vllm` 采用了以下核心技术：- **vllm 库**：用于加速 GP

avatar AI Agent技术社区
cover

2025年8月SCI-炭黑四角蜂优化算法 Tetragonula carbonaria Optimization Algorithm-附Matlab免费代码

avatar AI Agent技术社区

AgentScope示例应用：多智能体对话

在人工智能快速发展的今天，单一智能体已经难以满足复杂任务的需求。想象一下这样的场景：一个项目团队需要讨论技术方案，不同专业背景的成员各抒己见，最终达成共识。这正是多智能体对话要解决的问题——让多个AI智能体像真实团队成员一样进行有意义的交流。AgentScope作为面向开发者的多智能体编程框架，提供了强大的多智能体对话能力。本文将深入探讨如何使用AgentScope构建高效的多智能体对话系统。..

avatar AI Agent技术社区