1. Toy模板网首页
  2. > Toy博客

图论---最短路问题

9月前 作者：Y丶bs 分类：Toy博客 阅读(29) 违法举报

这篇具有很好参考价值的文章主要介绍了图论---最短路问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

  • 单源最短路 n: 点的数量 m: 边的数量

    • 所有边权都是正数

      • (1)朴素Dijkstra算法 O(n^2)

      • (2)堆优化版的Dijkstra算法 O(mlogn)

    • 存在负权边

      • (1)Bellmax-Fold O(nm) (让选择不超过k条边的时候使用)

      • (2)SPFA 一般O(m)，最坏O(nm)

  • 多源汇最短路

    • Floyd算法 O(n^3)

边权非负

朴素Dijkstra

每次找到距离起点最近的点，然后用这个点去更新其他点，时间复杂度为O(n^2)

Dijkstra求最短路 I
图论---最短路问题

import java.io.*;
import java.util.*;

class Main{
    static final int N = 510;
    static boolean[] st = new boolean[N];
    static int[] dist = new int[N];
    static int[][] g = new int[N][N];
    static int n, m;
    
    public static void Dijkstra(){
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        
        for (int i = 0; i < n; i++) {
            int t = -1;
            for(int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[j] < dist[t]))
                    t = j;
            }
            
            st[t] = true;
            for (int j = 1; j <= n; j++)
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
        }
        
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        
        for (int i = 0; i <= n; i++){
            Arrays.fill(g[i], 0x3f3f3f3f);
            g[i][i] = 0;
        }
        for (int i = 0; i < m; i++) {
            str = br.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int y = Integer.parseInt(str[1]);
            int z = Integer.parseInt(str[2]);
            g[x][y] = Math.min(g[x][y], z);
        }
        
        Dijkstra();
        if (dist[n] == 0x3f3f3f3f) System.out.println(-1);
        else System.out.println(dist[n]);
    }
}

堆优化版Dijkstra

朴素Dijkstra算法，找最近的点需要n次，更新边需要m次，所以总体是O(n^2)

如果用堆优化，找最短的点是O(1),找n次; 更新边是O(logn),更新m次(外层循环是n个点,每次更新的是这个点的连边, 所有点的连边加起来一共m条)，时间复杂度为O(mlogn)

不用手写堆，可以用优先队列实现,优先队列不能修改元素，因此需要修改元素就直接插入，因此会有冗余元素存在。手写堆的话，在排序的时候还要交换下标

Dijkstra求最短路 II
图论---最短路问题

import java.io.*;
import java.util.*;

class Main {
    static final int N = 150010;
    static int[] h = new int[N], e = new int[N], ne = new int[N], w = new int[N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int n, m, idx;
    
    public static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    public static void Dijkstra(){
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        PriorityQueue<PII> q = new PriorityQueue<>((o1, o2) -> o1.d - o2.d);
        
        q.offer(new PII(0, 1));
        while (!q.isEmpty()){
            PII t = q.poll();
            int dis = t.d;
            int ver = t.u;
            if (st[ver]) continue;
            st[ver] = true;
            
            // 用点ver更新距离
            for (int i = h[ver]; i != -1; i = ne[i]) {
                int u = e[i];
                if (dist[u] > dis + w[i]) {
                    dist[u] = dis + w[i];
                    q.offer(new PII(dist[u], u));
                }
            }
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        
        Arrays.fill(h, -1);
        for (int i = 0; i < m; i++) {
            str = br.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int y = Integer.parseInt(str[1]);
            int z = Integer.parseInt(str[2]);
            add(x, y, z);
        }
        
        Dijkstra();
        if (dist[n] == 0x3f3f3f3f) System.out.println(-1);
        else System.out.println(dist[n]);
        
    }
}

class PII{
    public int d;
    public int u;
    public PII(int d, int u) {
        this.d = d;
        this.u = u;
    }
}


边权有负值

Bellman-ford

该算法可来求经过k条边的最短路问题，边权可以为负。也可以用来求是否存在负环，但是求负环一般用spfa，Bellman-ford的时间复杂度为O(mn)

算法流程
1、for n 次 ; 迭代k次表示：从1号点经过了不超过k条边到其他点的距离；如果第n次更新时，
dist还发生变化(经过了n条边，有n+1个点，则一定有两个点一样)，说明存在负权边的环

2、for 所有边 a->b--w dist[b]=min(dist[b],dist[a]+w)

last数组存的是dist上一次更新的备份,假设1->2=1,2->3=1，初始dist[2]=+00,
第一次更新dist[2]=1,更新dist[3]时，就用dist[2]来更新了，所以应该用上一次的结果更新

有边数限制的最短路
图论---最短路问题

import java.io.*;
import java.util.*;

class Main {
    static final int N = 510, M = 10010;
    static int[] dist = new int[N];
    static int[] last = new int[N];
    static node[] g = new node[M];
    static int n, m, k;
    
    public static void bellman_fold(){
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        for (int i = 0; i < k; i++) {
            last = Arrays.copyOf(dist, dist.length);
            for (int j = 0; j < m; j++) {
                int a = g[j].a;
                int b = g[j].b;
                int c = g[j].c;
                if (dist[b] > last[a] + c){
                    dist[b] = last[a] + c;
                }
            }
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        k = Integer.parseInt(str[2]);
        
        for (int i = 0; i < m; i++) {
            str = br.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            int c = Integer.parseInt(str[2]);
            g[i] = new node(a, b, c);
        }
        
        bellman_fold();
        if (dist[n] > 0x3f3f3f3f / 2) System.out.println("impossible");
        else System.out.println(dist[n]);
    }
}

class node{
    int a;
    int b;
    int c;
    public node(int a, int b, int c){
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

spfa

spfa是对bellman-Fold进行优化，bellman-Fold每次对所有边进行迭代，

dist[y] = min(dist[y], last[x] + w); 如果last[x]没有变化，那么dist[y]也不需要更新

因此每次只需要将变化过的点放入队列，每次从队列取来更新后边的点即可

这里的st数组标记的是该点是否在队列中

spfa时间复杂度一般是O(m), 最坏是O(nm)

spfa求最短路

图论---最短路问题

import java.io.*;
import java.util.*;

class Main{
    static final int N = 100010;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int[] h = new int[N], e = new int[N], ne = new int[N], w = new int[N];
    static int n, m, idx;
    
    public static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    public static void spfa(){
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        st[1] = true;
        
        while (!q.isEmpty()){
            int t = q.poll();
            st[t] = false;
            
            for (int i = h[t]; i != -1; i = ne[i]) {
                int u = e[i];
                if (dist[u] > dist[t] + w[i]){
                    dist[u] = Math.min(dist[u], dist[t] + w[i]);
                    if (!st[u]) {
                        q.offer(u);
                        st[u] = true;
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        
        Arrays.fill(h, -1);
        for (int i = 0; i < m; i++) {
            str = br.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int y = Integer.parseInt(str[1]);
            int z = Integer.parseInt(str[2]);
            add(x, y, z);
        }
        
        spfa();
        if (dist[n] == 0x3f3f3f3f) System.out.println("impossible");
        else System.out.println(dist[n]);
        
    }
}

spfa判断负环

维护一个cnt数组即可，cnt[i]表示从1-i经过了多少条边，如果边数大于等于n，说明存在负环

spfa判断负环

图论---最短路问题

import java.io.*;
import java.util.*;

class Main {
    static final int N = 2010, M = 10010;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M], cnt = new int[N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int n, m, idx;
    
    public static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    public static boolean spfa(){
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        Queue<Integer> q = new LinkedList<>();
        // 因为有的负环可能从点1无法到达，所以将所有点都加入队列
        for (int i = 1; i <= n; i++){
            q.offer(i);
            st[i] = true;
        }
        
        while (!q.isEmpty()){
            int t = q.poll();
            st[t] = false;
            
            for (int i = h[t]; i != -1; i = ne[i]) {
                int u = e[i];
                if (dist[u] > dist[t] + w[i]) {
                    dist[u] = dist[t] + w[i];
                    cnt[u] = cnt[t] + 1;
                    if (cnt[u] >= n)
                        return true;
                    if (!st[u]) {
                        q.offer(u);
                        st[u] = true;
                    }
                }
            }
        }
        return false;
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str[] = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        
        Arrays.fill(h, -1);
        for (int i = 0; i < m; i++) {
            str = br.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int y = Integer.parseInt(str[1]);
            int z = Integer.parseInt(str[2]);
            add(x, y, z);
        }
        
        if (spfa()) System.out.println("Yes");
        else System.out.println("No");
        
    }
}


多源汇最短路

Floyd

Floyd实际上是一个dp问题

  • 状态表示: f[k, i, j]表示从i到j,中间点只经过1到k(不包括i和j)的所有路径最小值

  • 状态计算: f[k, i, j] = min(f[k-1, i, j], f[k-1, i, k] + f[k-1, k, j])

f[k-1, i, j]表示不经过第k个点,f[k-1, i, k] + f[k-1, k, j]表示经过第k个点

可以发现f[k, i, j]只和k-1层有关系，所以第一维可以去掉

f[i][j] = min(f[i][j], f[i][k] + f[k][j])

f[i][j]一定是属于第k-1层的，而f[i][k]不一定属于k-1层，如果k小于j，那么f[i][k]属于第k层,即f[k, i, k] + f[k-1, k, j]

如果有负环，则一定不存在最短路，但是存在最短路，说明从i到j一定存在一条路径不包括重复点且最短.所以f[k,i,k]表示从i走到k，将1到k作为中间点，如果将k作为中间点，即k到k为一个环，更新最短路时会去点这个负环，所以此时答案不会被影响

Floyd求最短路

图论---最短路问题文章来源地址https://www.toymoban.com/news/detail-454074.html

import java.io.*;
import java.util.*;

class Main{
    static final int N = 210;
    static int[][] dist = new int[N][N];
    static int n, m, k;
    
    public static void Floyd(){
        for (int k = 1; k <= n; k++) 
            for (int i = 1; i <= n; i++) 
                for (int j = 1; j <= n; j++)
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);    
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str[] = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        k = Integer.parseInt(str[2]);
        
        for (int i = 1; i <= n; i++){
            Arrays.fill(dist[i], 0x3f3f3f3f);
            dist[i][i] = 0;
        }
        for (int i = 0; i < m; i++) {
            str = br.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int y = Integer.parseInt(str[1]);
            int z = Integer.parseInt(str[2]);
            dist[x][y] = Math.min(dist[x][y], z);
        }
        
        Floyd();
        
        for (int i = 0; i < k; i++) {
            str = br.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int y = Integer.parseInt(str[1]);
            if (dist[x][y] >= 0x3f3f3f3f / 2) System.out.println("impossible");
            else System.out.println(dist[x][y]);
        }
    }
}

到了这里，关于图论---最短路问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 算法提高-图论-单源最短路的建图方式

    算法提高-图论-单源最短路的建图方式

    建图 找出一个牧场，它到其他牧场的距离之和最小 我是这么理解的，djsktra是一个贪心的思想，加法里面不能加负数我就不说了 求乘法最大值的时候为什么边权必须0-1，因为在乘法最大值里面有一个边权大于1的话那不就等价于求加法最小值的时候有一个边权为负数的么，d

    2024年02月08日
    浏览(44)
  • 【单源最短路 图论】882. 细分图中的可到达节点

    【单源最短路 图论】882. 细分图中的可到达节点

    视频算法专题 单源最短路 图论 给你一个无向图（原始图），图中有 n 个节点，编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链，每条边之间的新节点数各不相同。 图用由边组成的二维数组 edges 表示，其中 edges[i] = [ui, vi, cnti] 表示原始图中节点 ui 和 vi 之间存在

    2024年04月10日
    浏览(42)
  • 图论算法基础:单源最短路径Dijkstra算法分析

    图论算法基础:单源最短路径Dijkstra算法分析

    在 有向带权图 中给定一个起始顶点(源点),Dijkstra算法可以求出 所有其他顶点 到源点的最短路径,Dijkstra算法 不能用于同时含有正负权值的边的图 Source 顶点集合:已经确定 到源点的最短路径 的顶点就会加入 Source 集合中, Source 集合初始时只有源点 dist 数组:用于记录每个顶点到

    2024年02月11日
    浏览(42)
  • 单源最短路（只有一个起点）bfs，多源BFS，目录力扣675.为高尔夫比赛砍树，多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量

    单源最短路（只有一个起点）bfs，多源BFS，目录力扣675.为高尔夫比赛砍树，多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量

    目录 力扣675.为高尔夫比赛砍树 多源最短路问题: 力扣542.01矩阵 力扣1020.飞地的数量 Collections.sort(trees,(a,b)-{                    return f.get(a[0]).get(a[1])-f.get(b[0]).get(b[1]);                }); 这块比较难写 这段代码是Java中的一段代码，用于对名为trees的集合进行排序。这个集

    2024年04月12日
    浏览(67)
  • 第三章 图论 No.1单源最短路及其综合应用

    第三章 图论 No.1单源最短路及其综合应用

    做乘法的最短路时，若权值=0，只能用spfa来做，相等于加法中的负权边 1129. 热浪 1129. 热浪 - AcWing题库 单源最短路，稀疏图，用堆优化Dijkstra即可，就是板子套了个背景 debug：由于是无向图，边的数量要开两倍。但是 w[N] 没改，debug了很久 所以 e[M], ne[M], w[M] ，只有 h[N] ，其他

    2024年02月14日
    浏览(46)
  • 【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树

    【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树

    ✅作者简介：热爱后端语言的大学生，CSDN内容合伙人 ✨精品专栏：C++面向对象 🔥系列专栏：算法百炼成神 本专栏收录的均为牛客网的算法题目，内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目，也有大厂的面

    2024年02月03日
    浏览(45)
  • 第三章 图论 No.2单源最短路之虚拟源点，状压最短路与最短路次短路条数

    第三章 图论 No.2单源最短路之虚拟源点，状压最短路与最短路次短路条数

    dp是特殊的最短路，是无环图（拓扑图）上的最短路问题 1137. 选择最佳线路 1137. 选择最佳线路 - AcWing题库 对于每组测试数据，该重置的数据要重置，我没有重置idx，导致TLE 处理反向建图，还有一种扩展做法：虚拟源点 设置虚拟源点，与每个起点之间连接边权为0的边 原问题

    2024年02月14日
    浏览(48)
  • 单源最短路径问题——分支限界法（Java）

    单源最短路径问题——分支限界法（Java）

    1.1 分支限界法求解目标 分支限界法与回溯法的不同求解目标： 回溯法的求解目标：找出解空间树中满足约束条件的 所有解 ； 分支限界法的求解目标：找出满足约束条件的 一个解 ，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下

    2024年02月06日
    浏览(35)
  • 最短路问题 Bellman-Ford（单源最短路径）(图解)

    最短路问题 Bellman-Ford（单源最短路径）(图解)

    对于边(u,v)，用dist（u）和（u，v）的和尝试更新dist（v）:                          dist(v) = min(dist(v) , dist(u)+l(u,v) 注：dist（i）为源点（起点）到i点的距离，l（u，v）为u-v的边权。 Bellman-Ford的基本操作是进行多次迭代，每一轮迭代对图上所有边进行松弛操作，直到

    2024年02月09日
    浏览(38)
  • 数据结构学习记录——图-最短路径问题（无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra（迪杰斯特拉）算法、Floyd算法）

    数据结构学习记录——图-最短路径问题（无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra（迪杰斯特拉）算法、Floyd算法）

    目录 问题分类  无权图单源最短路径算法 思路 伪代码 时间复杂度 代码实现（C语言） 有权图单源最短路径算法 Dijkstra（迪杰斯特拉）算法 伪代码  时间复杂度  代码实现（C语言） 多源最短路径算法 两种方法 Floyd算法 代码实现（C语言） 最短路径问题的抽象 在网络中，求

    2024年02月08日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包