Day65_20250213图论part9_dijkstra(堆优化版)|Bellman_ford算法精讲

Day65_20250213图论part9_dijkstra(堆优化版)|Bellman_ford算法精讲

dijkstra(堆优化版)

题目

https://www.programmercarl.com/kamacoder/0047.%E5%8F%82%E4%BC%9Adijkstra%E5%A0%86.html

小明参加科学大会

思路

• 思路

  • 朴素版的dijkstra，时间复杂度为O(n^2)，与节点数量有关系

  • 从边的数量出发来优化算法

    • 当n很大，边数量也很大，保持原算法。
    • 当n很小，边很小(稀疏图)，从边的角度来求最短路。

  • 图的存储

    • 邻接矩阵
      • 二维数组，节点角度，有多少节点就申请多大的二维数组。
      • 缺点
        • 稀疏图，边少节点多，申请过大的二维数组，空间浪费
        • 时间复杂度n*n
      • 优点
        • 简单
        • 检查任意两个顶点间是否存在边的操作非常快
        • 适合稠密图(边数接近顶点数平方)
    • 邻接表 数组+链表
      • 从边的数量来表示图，边数量决定链表大小
      • 优点：
        • 稀疏图(边少节点多)的存储，只要存储边，空间利用率高
        • 遍历节点的链接情况更容易
      • 缺点：
        • 检查任意两个节点间是否存在边，效率相对低，时间复杂度O(V),V表示某节点连接其他节点的数量
        • 实现复杂，不易理解

  • 三部曲(从节点角度)

    • 选源点到哪个节点近且该节点未被访问过。
    • 该最近节点被标记访问过
    • 更新非访问节点到源点的距离(更新minDist数组)

  • 三部曲(从边角度) 稀疏图

    • 直接把边(带权值)加入到小顶堆(利用堆来自动排序)，每次从堆顶里取出边自然是距离源点最近的节点所在的边。
      • 不需要两层for循环
    • 用邻接表来表述图结构，链表中的数是一个键值对
      • 
      • 在代码中使用pair <int,int>容易搞混int的两个表示，代码可读性查，可以自定义一个类来取代pair<int,int>结构体

• 细节

  • 遍历节点用for循环，而遍历边遍历的是链表grid[cur节点编号] 【要对邻接表的表达方式有了解】

    • for (Edge edge : grid[cur.first])
    • pair<节点编号，源点到该节点的权值>

  • 与朴素版的dijkstra

    • 邻接表的表示方式不同
    • 使用优先级队列(小顶栈)来堆新链接的边排序
    • 复杂度
      • 时间复杂度：O(ElogE) E为边的数量
      • 空间复杂度：O(N+E) N为节点的数量

• 代码

  import java.util.*;
  public class Main{public static void main(String[] args){//输入Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();int m=scanner.nextInt();//边List<List<Edge>> grid=new ArrayList<>(n+1);for(int i=0;i<=n;i++){grid.add(new ArrayList<>());}for(int i=0;i<m;i++){int p1=scanner.nextInt();int p2=scanner.nextInt();int val=scanner.nextInt();grid.get(p1).add(new Edge(p2,val));}//起点和终点int start=1;int end=n;//存储从源点到每个节点的最短距离int[] minDist=new int[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);//记录顶点是否被访问过boolean[] visited=new boolean[n+1];//优先队列中存放Pair<节点，源点到该节点的权值?PriorityQueue<Pair<Integer,Integer>> pq=new PriorityQueue<>(new MyComparison());//初始化队列，源点到源点的距离为0，初始为0pq.add(new Pair<>(start,0));minDist[start]=0;//起始点到自身的距离为0//当小顶栈不为空while(!pq.isEmpty()){//1.第一步，选源点到哪个节点近&&未被访问过(优先级队列实现)Pair<Integer,Integer> cur=pq.poll();if(visited[cur.first])   continue;//第二步，该最近节点被标记访问过visited[cur.first]=true;//第三步，更新非访问节点到源点的距离(更新minDist数组)for(Edge edge:grid.get(cur.first)){//选中的cur节点未被访问&&【新路径比之前更短】源点到当前节点的最短距离加上当前节点的值比之前的更小if(!visited[edge.to]&&minDist[cur.first]+edge.val<minDist[edge.to]){minDist[edge.to]=minDist[cur.first]+edge.val;//更新//为了确保下一次能够处理这个新的最短路径，必须将更新后的节点重新放入优先队列。pq.add(new Pair<>(edge.to,minDist[edge.to]));}}}//打印if(minDist[end]==Integer.MAX_VALUE){System.out.println(-1);//不能到达终点}else{System.out.println(minDist[end]);//到达终点最短路径}}
  }
  //结构体
  class Edge{int to;//邻接顶点int val;//边的权重Edge(int to,int val){this.to=to;this.val=val;}
  }class MyComparison implements Comparator<Pair<Integer, Integer>> {@Overridepublic int compare(Pair<Integer, Integer> lhs, Pair<Integer, Integer> rhs) {return Integer.compare(lhs.second, rhs.second);}
  }class Pair<U, V> {public final U first;public final V second;public Pair(U first, V second) {this.first = first;this.second = second;}
  }

总结

• 与朴素版的代码，邻接表的表示方式不同。
• 使用优先级队列(小顶栈)来堆新链接的边排序

Bellman_ford算法

题目

【城市间货物运输I】

题目描述

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

网络中的道路都有各自的运输成本和政府补贴， 道路的权值计算方式为：运输成本 - 政府补贴 。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。

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

输入描述

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

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

输出描述

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

输入示例

6 7
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5

输出示例

1

提示信息

示例中最佳路径是从 1 -> 2 -> 5 -> 6，路上的权值分别为 1 2 -2，最终的最低运输成本为 1 + 2 + (-2) = 1。

示例 2：

4 2
1 2 -1
3 4 -1

在此示例中，无法找到一条路径从 1 通往 4，所以此时应该输出 “unconnected”。

数据范围：

1 <= n <= 1000；
1 <= m <= 10000;

-100 <= v <= 100;

思路

• 思路

  • **【带负权值的单源最短路问题】**单源最短路问题，边的权值是有负数的。【运输的过程中政府补贴>运输成本】

  • 核心：****【松弛】****对所有边进行松弛n-1次操作(n为节点数量)，从而求得目标最短路。

    • if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value
    • 状态一：:minDist[A]+valur推出minDist[B] 状态二：minDist[B]本身就有权值(其他边连接到节点C，minDist[B]记录了其他边到minDist[B]的权值)
    • minDist[B]=min(minDist[A]+value,minDist[B]);
    • 动态规划：将一个问题分解成多个决策阶段，通过状态之间的递归关系最后计算出全局最优解。、

  • 为什么是n-1次松弛？

    • 对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离。
    • 对所有边松弛n-1次，得到与起点n-1边相连的节点的最短距离。
    • 节点数量是n，从起点到终点最多是n-1条边相连。无论图是什么样的，边是什么样的顺序，对所有边松弛n-1次就一定能得到起点到终点的最短距离。
    • 当松弛大于n-1次，minDist数组就不会变化了。同时保证道路网络中不存在任何负权回路(在有向图中出现有向环且环的总权值为负数)，只需要松弛n-1次就能得到结果，不需要松弛更多次了。

  • 复杂度

    • 时间复杂度：O(N*E)，N为节点数量，E是图中边的数量
    • 空间复杂度：O(N),N节点，minDist数组所开辟的空间
• 代码

  import java.util.*;public class Main{public static void main(String[] args){//输入Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();//节点int m=scanner.nextInt();//边List<Edge> edges=new ArrayList<>();for(int i=0;i<m;i++){int from=scanner.nextInt();int to=scanner.nextInt();int val=scanner.nextInt();edges.add(new Edge(from,to,val));}int[] minDist=new int[n+1];//从源点到当前节点的最短路径//初始化Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]=0;//从1开始//关键代码for(int i=1;i<n;i++){for(Edge edge:edges){//更新minDist矩阵//从遍历过的节点出发&&当前边的的起点+一个路径的终点的值<当前终点的//1.没有从源点到edge.from的有效路径。无法通过edge.from进行有效的路径更新//2.检查通过当前边edge是否可以得到更短的路径(如果这个路径长度<当前存储在minDist[edge.to]的值)if(minDist[edge.from]!=Integer.MAX_VALUE&&(minDist[edge.from]+edge.val)<minDist[edge.to]){//更新当前节点的最短路径，从A得到的B和B本身进行比较minDist[edge.to]=minDist[edge.from]+edge.val;}}}//打印结果if(minDist[n]==Integer.MAX_VALUE){System.out.println("unconnected");}else{System.out.println(minDist[n]);}}}class Edge{int from;int to;int val;public Edge(int from,int to,int val){this.from=from;this.to=to;this.val=val;}
  }
  

总结

• 掌握关键点