当前位置: 首页 > news >正文

代码训练营 day64|算法优化、带负权值图的最短路径

前言

这里记录一下陈菜菜的刷题记录,主要应对25秋招、春招
个人背景
211CS本+CUHK计算机相关硕,一年车企软件开发经验
代码能力:有待提高
常用语言:C++

系列文章目录

第64天 :第十一章:图论part09


`

文章目录

  • 前言
  • 系列文章目录
    • 第64天 :第十一章:图论part09
  • 一、今日任务
  • 二、详细布置
      • dijkstra(堆优化版)精讲
        • 模板
      • Bellman_ford 算法精讲
        • 模板
        • 提示:
        • 样例1:
    • 总结



一、今日任务

● dijkstra(堆优化版)精讲
● Bellman_ford 算法精讲

二、详细布置

dijkstra(堆优化版)精讲

朴素版的dijkstra的时间复杂度为 O(n^2),可以看出时间复杂度 只和 n (节点数量)有关系。如果n很大的话,我们可以换一个角度来优先性能。

用堆优化算法

模板
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std; 
// 小顶堆
class mycomparison {
public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}
};
// 定义一个结构体来表示带权重的边
struct Edge {int to;  // 邻接顶点int val; // 边的权重Edge(int t, int w): to(t), val(w) {}  // 构造函数
};int main() {int n, m, p1, p2, val;cin >> n >> m;vector<list<Edge>> grid(n + 1);for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val; // p1 指向 p2,权值为 valgrid[p1].push_back(Edge(p2, val));}int start = 1;  // 起点int end = n;    // 终点// 存储从源点到每个节点的最短距离std::vector<int> minDist(n + 1, INT_MAX);// 记录顶点是否被访问过std::vector<bool> visited(n + 1, false); // 优先队列中存放 pair<节点,源点到该节点的权值>priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;// 初始化队列,源点到源点的距离为0,所以初始为0pq.push(pair<int, int>(start, 0)); minDist[start] = 0;  // 起始点到自身的距离为0while (!pq.empty()) {// 1. 第一步,选源点到哪个节点近且该节点未被访问过 (通过优先级队列来实现)// <节点, 源点到该节点的距离>pair<int, int> cur = pq.top(); pq.pop();if (visited[cur.first]) continue;// 2. 第二步,该最近节点被标记访问过visited[cur.first] = true;// 3. 第三步,更新非访问节点到源点的距离(即更新minDist数组)for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点,cur指向的节点为 edge// cur指向的节点edge.to,这条边的权值为 edge.valif (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDistminDist[edge.to] = minDist[cur.first] + edge.val;pq.push(pair<int, int>(edge.to, minDist[edge.to]));}}}if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点else cout << minDist[end] << endl; // 到达终点最短路径
}

Bellman_ford 算法精讲

经典的带负权值的单源最短路问题,此时就轮到Bellman_ford登场了.
Bellman_ford算法 也是采用了动态规划的思想,即:将一个问题分解成多个决策阶段,通过状态之间的递归关系最后计算出全局最优解。

bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作(n为节点数量),从而求得目标最短路。

如果 通过 A 到 B 这条边可以获得更短的到达B节点的路径,即如果 minDist[B] > minDist[A] + value,那么我们就更新 minDist[B] = minDist[A] + value ,这个过程就叫做 “松弛” 。

对所有边松弛一次,相当于计算 起点到达 与起点一条边相连的节点 的最短距离。
那对所有边松弛两次 可以得到与起点 两条边相连的节点的最短距离。
那对所有边松弛三次 可以得到与起点 三条边相连的节点的最短距离.

那么无论图是什么样的,边是什么样的顺序,我们对所有边松弛 n-1 次 就一定能得到 起点到达 终点的最短距离。

其实也同时计算出了,起点 到达 所有节点的最短距离,因为所有节点与起点连接的边数最多也就是 n-1 条边。

模板
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid;// 将所有边保存起来for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;// p1 指向 p2,权值为 valgrid.push_back({p1, p2, val});}int start = 1;  // 起点int end = n;    // 终点vector<int> minDist(n + 1 , INT_MAX);minDist[start] = 0;for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次for (vector<int> &side : grid) { // 每一次松弛,都是对所有边进行松弛int from = side[0]; // 边的出发点int to = side[1]; // 边的到达点int price = side[2]; // 边的权值// 松弛操作 // minDist[from] != INT_MAX 防止从未计算过的节点出发if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) { minDist[to] = minDist[from] + price;  }}}if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点else cout << minDist[end] << endl; // 到达终点最短路径}

题目链接:94
文章讲解:图文讲解

题目描述

某国为促进城市间经济交流,决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市,通过道路网络连接,网络中的道路仅允许从某个城市单向通行到另一个城市,不能反向通行。

网络中的道路都有各自的运输成本和政府补贴,道路的权值计算方式为:运输成本 - 政府补贴。

权值为正表示扣除了政府补贴后运输货物仍需支付的费用;权值为负则表示政府的补贴超过了支出的运输成本,实际表现为运输过程中还能赚取一定的收益。

请找出从城市 1 到城市 n 的所有可能路径中,综合政府补贴后的最低运输成本。

如果最低运输成本是一个负数,它表示在遵循最优路径的情况下,运输过程中反而能够实现盈利。

城市 1 到城市 n 之间可能会出现没有路径的情况,同时保证道路网络中不存在任何负权回路。
输入描述

第一行包含两个正整数,第一个正整数 n 表示该国一共有 n 个城市,第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行,每行包括三个整数,s、t 和 v,表示 s 号城市运输货物到达 t 号城市,道路权值为 v(单向图)。

输出描述

如果能够从城市 1 到连通到城市 n, 请输出一个整数,表示运输成本。如果该整数是负数,则表示实现了盈利。如果从城市 1 没有路径可达城市 n,请输出 “unconnected”。

提示:

数据范围:
1 <= n <= 1000;
1 <= m <= 10000;
-100 <= v <= 100;

样例1:
输入:
6 7
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5输出:
1    

总结

今天主要学习了最短路径的一系列操作,包括带负权值的图的一系列操作,今天有点难,二刷加油。
加油,坚持打卡的第64天。


http://www.mrgr.cn/news/71845.html

相关文章:

  • 产品经理如何提升项目管理能力
  • 在 .NET 6.0 中创建用于 CRUD 操作的 Web API
  • 【JavaScript】
  • PICO+Unity MR空间锚点
  • SL1571B 输入5V2A或单节锂电池,升压12V 10W 升压恒压芯片
  • 【go从零单排】Random Numbers、Number Parsing
  • 一维前缀和/差分,二维前缀和/差分
  • 【时时三省】(C语言基础)函数介绍strtok
  • 概率论中的PMF、PDF和CDF
  • 关于CJS,AMD,CMD,UMD的了解
  • 推荐一款强大的行车记录仪播放器:Dashcam Viewer Plus
  • Java小型项目-音乐评论分析
  • 论文解读:CARAT
  • cache(五)Write-through,Write-back,Write-allocate,No-write-allocate
  • 【t365】基于springboot的高校疫情防控系统
  • uniapp路由与页面跳转详解:API调用与Navigator组件实战
  • linux性能提升之sendmmsg和recvmmsg
  • kafka夺命连环三十问(16-22)
  • A/B测试的误区与优化策略:如何最大化客户留存ROI?
  • 【LeetCode】【算法】136. 只出现一次的数字
  • 数据结构《链表》
  • ML 系列: 第 23 节 — 离散概率分布 (多项式分布)
  • 【MySQL 保姆级教学】事务的自动提交和手动提交(重点)--上(13)
  • 移动电源测试中最核心的测试项目有哪些?-纳米软件
  • 多线程和线程同步复习
  • 鸿蒙next版开发:ArkTS组件通用属性(Flex布局)