最短路径算法

🕗 发布于 2025-01-14 01:26 c++ 算法

关注：算法思路，时间复杂度，适用情况（单源/多源，负边权/负边权回路）

复习弗雷德算法--基于动态规划--多源--负边权--时间复杂度O(v^3)

int的最大值是0x7fffffff

#include <iostream>  
using namespace std;
#define inf 100000
int n, m;
int a[105][105];
int dp[105][105];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = inf;
            if (i == j) {
                a[i][j] = 0;
            }
        }
    }
    int x, y, w;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y >> w;
        a[x][y] = w;
    }
    //初始化dp
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = a[i][j];
        }
    }
    for (int k = 1; k <= n; k++) {//枚举中转点
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = min(dp[i][j], dp[k - 1][i] + dp[k][j]);//不能交换循环位置，无法解释了
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

复习迪斯拉算法--基于贪心--单源--不能处理负边权--时间复杂度O(v^3)

#include<iostream>
using namespace std;
#define INF 65535
int g[105][105];
int dist[105], path[105];
int flag[105];//==1  i的最短路径已经确定
int n, m;
void Dijkstra(int s) {
//起点到起点
flag[s] = 1;
dist[s] = 0;
path[s] = s;
int minn = INF;
int t;
for (int i = 1; i < n; i++) {//循环n-1次
minn = INF;
for (int j = 0; j < n; j++) {
if (flag[j] == 0 && dist[j] < minn) {
minn = dist[j];
t = j;//t点是dist最小的点
}
}
flag[t] = 1;//确定最小路径
for (int j = 0; j < n; j++) {
if (flag[j] == 0 && dist[j] > (dist[t] + g[t][j])) {
dist[j] = dist[t] + g[t][j];
path[j] = t;
}
}
}

}
int main() {
int s;//起点
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)g[i][j] = 0;
else g[i][j] = INF;
}
}
int x, y, w;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> w;
g[x][y] = g[y][x] = w;
}
cin >> s;
dist[s] = 0;
for (int i = 0; i < n; i++) {
dist[i] = g[s][i];
if (g[s][i] == INF) {
path[i] = -1;
}
else {
path[i] = s;
}
}
Dijkstra(s);
for (int i = 0; i < n; i++) {
cout << "s到" << i << "的最短路径长度是" << dist[i] << ":";
//倒叙输出路径
cout << i << " ";
int j = i;
while (path[j] != j) {
cout << path[j] << " ";
j = path[j];
}
cout << endl;
}

return 0;
}
//9 16
//0 1 1
//0 2 5
//1 2 3
//1 3 7
//1 4 5
//2 4 1
//2 5 7
//3 4 2
//3 6 3
//4 5 3
//4 6 6
//4 7 9
//5 7 5
//6 7 2
//6 8 7
//7 8 4
//0

优化：无序找最小(通过小顶堆)--邻接表存图--链式前向星--priority_quque从n到logn

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
int n, m, cut;
int flag[105];
int dis[105];
int s;//起点
struct Edge {
int to, next, w;
}e[10005];
int head[105];
priority_queue<PII, vector<PII>, greater<PII>>q;
void add(int x,int y,int w) {
cut++;//从1开始
e[cut].to = y;
e[cut].w = w;
e[cut].next = head[x];
head[x] = cut;
cut++;
}

void dijkstra() {
memset(dis, 0x3f3f3f3f, sizeof(dis));
dis[s] = 0;
q.push({ 0,s });
while (q.size()) {
PII t = q.top();
q.pop();
int u = t.second, d = t.first;
if (flag[u] == 1)continue;
flag[u] = 1;
for (int i = head[u]; i != -1; i = e[i].next) {
//i即u的出边
int v = e[i].to;//u的邻接点
if (flag[v] == 0 && dis[v] > dis[u] + e[i].w) {
dis[v] = dis[u] + e[i].w;
q.push({ dis[v],v });
}
}
}
}
int main() {
scanf("%d %d %d", &n, &m, &s);
int x, y, w;
memset(head, -1, sizeof(head));
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &x, &y, &w);
add(x, y, w);
}
dijkstra();
for (int i = 1; i <= n; i++) {
printf("%d ", dis[i]);
}
return 0;
}
//4 5 1
//1 2 1
//1 4 1
//2 3 2
//4 3 2
//1 3 6

弗雷德和迪斯拉算法共性

福特算法Bellman-Ford算法--暴力遍历无脑松弛--单源--时间复杂度O(ve)--能处理负边权--不能处理负权回路，但是能判断是否有负权回路（让他循环到n次）

#include<iostream>
#include<vector>
using namespace std;
int n, m;
int dis[105];
int s;//起点
struct Edge {
int a, b, w;
}e[10005];
void ford() {
int x, y, w;
bool flag = 0;
for (int i = 1; i <= n - 1; i++) {
flag = 0;
for (int j = 0; j < m; j++) {
x = e[j].a;
y = e[j].b;
w = e[j].w;
if (dis[x] + w < dis[y]) {
dis[y] = dis[x] + w;
flag = 1;
}
}
if (flag == 0)break;//没有松弛操作，说明全部已经松弛了
}
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].w);
}
scanf("%d", &s);
memset(dis, 0x3f3f3f3f, sizeof(dis));
dis[s] = 0;
ford();
for (int i = 1; i <= n; i++) {
printf("%d ", dis[i]);
}
return 0;
}
//5 5
//2 3 2
//1 2 - 3
//1 5 5
//4 5 2
//3 4 3
//1

下面改一点点能判断有负权回路（负环）

#include<iostream>
#include<vector>
using namespace std;
int n, m;
int dis[105];
int s;//起点
struct Edge {
int a, b, w;
}e[10005];
void ford() {
int x, y, w;
bool flag = 0;
for (int i = 1; i <= n; i++) {//执行第n次
flag = 0;
for (int j = 0; j < m; j++) {
x = e[j].a;
y = e[j].b;
w = e[j].w;
if (dis[x] + w < dis[y]) {//第n次不执行松弛操作
dis[y] = dis[x] + w;
flag = 1;
}
}
//if (flag == 0)break;//没有松弛操作，说明全部已经松弛了
}
if (flag == 1)printf("有负权回路");
else printf("没有负权回路");
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].w);
}
scanf("%d", &s);
memset(dis, 0x3f3f3f3f, sizeof(dis));
dis[s] = 0;
ford();
for (int i = 1; i <= n; i++) {
printf("%d ", dis[i]);
}
return 0;
}
//5 5
//2 3 2
//1 2 - 3
//1 5 5
//4 5 2
//3 4 3
//1

缺点：枚举顺序导致时间长一点,可以优化，优化后就是SPFA算法。

SPFA算法：能判断负环--时间复杂度难以计算

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
int n, m, cut;
int flag[105];
int dis[105];
int s;//起点
struct Edge {
int to, next, w;
}e[10005];
int head[105];
priority_queue<PII, vector<PII>, greater<PII>>q;
void add(int x,int y,int w) {
cut++;//从1开始
e[cut].to = y;
e[cut].w = w;
e[cut].next = head[x];
head[x] = cut;
cut++;
}
void SPFA() {
queue<int>q;
memset(dis, 0x3f3f3f3f, sizeof(dis));
dis[s] = 0;
flag[s] = 1;//标记s有没有被入队
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
flag[u] = 0;
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;//v是u的邻接点
if (flag[v] == 0 && dis[v] > dis[u] + e[i].w) {
dis[v] = dis[u] + e[i].w;
q.push(v);
flag[v] = 1;
}
}
}
}
int main() {
scanf("%d %d %d", &n, &m, &s);
int x, y, w;
memset(head, -1, sizeof(head));
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &x, &y, &w);
add(x, y, w);
}
SPFA();
for (int i = 1; i <= n; i++) {
printf("%d ", dis[i]);
}
return 0;
}
//5 5 1
//2 3 2
//1 2 - 3
//1 5 5
//4 5 2
//3 4 3

判负环加上use（以下代码只比上一个代码多use但是已经注释）

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
int n, m, cut;
int flag[105];
int dis[105];
//int use[105];//用于判断负环
int s;//起点
struct Edge {
int to, next, w;
}e[10005];
int head[105];
priority_queue<PII, vector<PII>, greater<PII>>q;
void add(int x,int y,int w) {
cut++;//从1开始
e[cut].to = y;
e[cut].w = w;
e[cut].next = head[x];
head[x] = cut;
cut++;
}
void SPFA() {
queue<int>q;
memset(dis, 0x3f3f3f3f, sizeof(dis));
dis[s] = 0;
flag[s] = 1;//标记s有没有被入队
//use[s]++;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
flag[u] = 0;
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;//v是u的邻接点
if (flag[v] == 0 && dis[v] > dis[u] + e[i].w) {
dis[v] = dis[u] + e[i].w;
q.push(v);
//use[v]++;
flag[v] = 1;
//if(use[v]>=n)
}
}
}
}
int main() {
scanf("%d %d %d", &n, &m, &s);
int x, y, w;
memset(head, -1, sizeof(head));
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &x, &y, &w);
add(x, y, w);
}
SPFA();
for (int i = 1; i <= n; i++) {
printf("%d ", dis[i]);
}
return 0;
}
//5 5 1
//2 3 2
//1 2 - 3
//1 5 5
//4 5 2
//3 4 3

时间复杂度吃瓜

原文地址：https://blog.csdn.net/2403_88875937/article/details/145098094

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：深度学习｜表示学习｜为什么要有激活函数？｜03
下一篇：蓝桥云客第 5 场算法季度赛

构建沉浸式汉语学习环境
系统通过API网关与现有教育平台（如Moodle）无缝集成，支持快速部署。持续学习机制确保内容与时俱进，每月自动更新流行语库与文化热点。的技术三角，构建沉浸式汉语学习环境。
阅读更多2025-01-22
弹框上传预览
【代码】弹框上传预览。
阅读更多2025-01-22
Python 字符串处理深度解析：高级操作技巧、性能优化与实用案例全解
在Python中，字符串（str）是用于表示文本数据的不可变序列类型。其定义方式灵活多样，既可以使用单引号'...'、双引号"..."也可借助三引号'''...'''或"
阅读更多2025-01-22
SELF-RAG: 通过自我反思学习检索、生成和批判——图文并茂总结
SELF-RAG 是一种创新的框架，通过按需检索和自我反思来提高 LLM 的生成质量和事实准确性。实验结果表明，SELF-RAG 在多个任务上均优于现有的 LLM 和 RAG 方法。SELF-RAG
阅读更多2025-01-22
【Nginx系列】Nginx配置超时时间
检查配置是否在正确的上下文中设置。确保没有其他与超时相关的指令冲突。确保每次修改后重载配置，并测试是否正确。检查错误日志了解更多超时信息。尝试这些步骤后，如果仍然无法生效，可以分享更详细的配置或错误日
阅读更多2025-01-22
机器学习-核函数（Kernel Function）
核函数（Kernel Function）是一种数学函数，主要用于将数据映射到一个更高维的特征空间，以便于在这个新特征空间中更容易找到数据的结构或模式。核函数的主要作用是在不需要显式计算高维特征空间的情
阅读更多2025-01-22
Android系统开发（二十）：字体活起来，安卓自定义字体改造指南
在安卓系统中，字体不仅是UI设计的基础，更是品牌和文化的延伸。过去，修改字体需要通过复杂的系统更新，甚至涉及底层操作，风险和成本极高。再到Android 15，可变字体支持和动态实例化技术大大提升了字
阅读更多2025-01-22
【力扣系列题目】不同路径组合总和最大连续1个数打家劫舍{持续更新中...}
【代码】【力扣系列题目】不同路径组合总和最大连续1个数打家劫舍{持续更新中...}
阅读更多2025-01-22
【专题】为2025制定可付诸实践的IT战略规划报告汇总PDF洞察（附原数据表）
在当今瞬息万变的商业环境中，制定有效的IT战略规划对于企业的成功与可持续发展至关重要。本报告深入探讨了制定IT战略规划的关键活动，旨在为企业和决策者提供全面且实用的指导。Gartner的《为2025制
阅读更多2025-01-22
stm32使用MDK5.35时遇到*** TOOLS.INI: TOOLCHAIN NOT INSTALLED
mdk5.35出现***TOOLS.INI:TOOLCHAINNOTINSTALLED的问题！以管理员身份重新打开MDK5.35.0.0，用keygen破解密码，但是一直提示我是没有破解成功。targ
阅读更多2025-01-22

最短路径算法

相关文章