最短路算法|个人学习生活记录小站

概览

ps：处理负回环路只是说找到回环路，存在负回环路的不存在最短路一说

单源最短路算法

Dijkstra

https://blog.csdn.net/qq_33359282/article/details/69664073

原理

从所有已知最优点（已经找到最小通往值）通向的最快到达的点，一定是最优点

步骤

优先队列放入起始点（s,0）
从优先队列中取出一个点（最快到达点），确定其为最优点
遍历该点的所有边，更新该点到导向点的最短距离，将导向点及最短距离放入优先队列（故而使用队列存储更优）
重复步骤2

代码实现

https://www.luogu.com.cn/problem/P3371

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int m = s.nextInt();
        int s1 = s.nextInt();
        List<Node>[] maps=new List[n+1];
        PriorityQueue<Node> queue = new PriorityQueue<>(Node::cp);
        List<Integer> vis = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            vis.add(-1);
        }
        for (int i = 0; i < m; i++) {
            Node t = new Node();
            t.s = s.nextInt();
            t.e = s.nextInt();
            t.v = s.nextInt();

            List<Node> nodes = maps[t.s];
            if (nodes == null) {
                nodes = new ArrayList<>();
                maps[t.s]=nodes;
            }
            nodes.add(t);
        }
        Node f = new Node();
        f.s = s1;
        f.v = 0;
        queue.add(f);
        while (queue.size() > 0) {
            Node t = queue.poll();
            if (vis.get(t.s) == -1) {
                vis.set(t.s, t.v);
            } else {
                continue;
            }
            int size = 0;
            if (maps[t.s]!=null) {
                size=maps[t.s].size();
            }
            for (int i = 0; i < size; i++) {
                Node x = new Node();
                Node node=maps[t.s].get(i);
                if (vis.get(node.e) != -1) {
                    continue;
                }
                x.s = node.e;
                x.v = t.v + node.v;
                queue.add(x);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (vis.get(i) == -1) {
                System.out.print("2147483647 ");
            } else {
                System.out.print(vis.get(i) + " ");
            }

        }
    }


}

class Node {
    int s;
    int e;
    int v;

    public static int cp(Node a, Node b) {
        return Integer.compare(a.v, b.v);
    }
}

链式前向星

链式前向星并不是一个很复杂的数据结构，实际上可以理解为通过数组来实现链表的一种方式

如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。
前向星固然好写，但效率并不高。
而在优化为链式前向星后，效率也得到了较大的提升。
虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。

https://blog.csdn.net/sugarbliss/article/details/86495945

Bellman-Ford

https://blog.csdn.net/yuewenyao/article/details/81026278

原理

对所有边进行一轮松弛，至少能够确定一个到该点的最短值（一条到某个点的最短路径），故而最多需要n-1次松弛就（确定无负环情况下，最后一次不必严证，同理，可验证有无负环）

步骤

所有边距离置无限大，其实点置0
遍历所有边，更新其最短值
步骤二重复n-1次

代码实现

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int m = s.nextInt();
        int s1 = s.nextInt();
        List<Node> list=new ArrayList<>();
        int[] d=new int[n+1];
        int max=2147483647;
        Arrays.fill(d,max);
        d[s1]=0;
        for(int i=0;i<m;i++){
            Node t=new Node();
            t.s=s.nextInt();
            t.e=s.nextInt();
            t.v=s.nextInt();
            list.add(t);
        }
        int flag=0;
        for(int i=0;i<n-1;i++){
            for (Node t : list) {
                if (d[t.s] != max && d[t.e] > d[t.s] + t.v) {
                    d[t.e] = d[t.s] + t.v;
                    flag = 1;
                }
            }
            if(flag==0){
                break;
            }
            else {
                flag=0;
            }
        }
        for(int i=1;i<=n;i++){
            System.out.print(d[i]+" ");
        }
    }
}
class Node {
    int s;
    int e;
    int v;
}

SPFA

https://blog.csdn.net/qq_44691917/article/details/104234394

原理

Bellman-Ford中可以发现，每次松弛最有效的是靠近最优点的那一批，而每次松弛都能确定一些最优点，这些最优点将不必重复计算。一个点为最优点，必然是没有其他点能够松弛他。

步骤

队列中放入初始点(s,0)
取出队列头部的点，遍历其通向列表，如果通向点可以被松弛（通向点距离>该点距离+边）且不在队列中，则将通向点加入队列。
重复步骤2，直至队列为空

代码实现

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int m = s.nextInt();
        int s1 = s.nextInt();
        List<Node>[] maps = new List[n + 1];
        Queue<Integer> queue=new LinkedList<>();
        int[] vis=new int[n+1];
        int[] d=new int[n+1];
        Arrays.fill(d,Integer.MAX_VALUE);
        d[s1]=0;
        for (int i = 0; i < m; i++) {
            Node t = new Node();
            t.s = s.nextInt();
            t.e = s.nextInt();
            t.v = s.nextInt();

            List<Node> nodes = maps[t.s];
            if (nodes == null) {
                nodes = new ArrayList<>();
                maps[t.s]=nodes;
            }
            nodes.add(t);
        }
        vis[s1]=1;
        queue.add(s1);
        while (!queue.isEmpty()){
            int t=queue.poll();
            vis[t]=0;
            List<Node> list=maps[t];
            for (Node node:list){
                if(d[node.s]+node.v<d[node.e]){
                    d[node.e]=d[node.s]+node.v;
                    if(vis[node.e]==0){
                        queue.add(node.e);
                    }
                }
            }
        }
        for(int i=1;i<=n;i++){
            System.out.print(d[i]+" ");
        }
    }
}
class Node {
    int s;
    int e;
    int v;
}

多源最短路

Floyd

https://houbb.github.io/2020/01/23/data-struct-learn-03-graph-floyd

原理

动态规划其转移方程为f[k][i][j]=min(f[k-1][i][j], f[k-1][i][k]+f[k-1][k][j])。表示经过前k个点帮助的情况下，i到j的最短距离。

最优子结构

比如一条从a到e的最短路a->b->c->d->e 那么 a->b->c 一定是a到c的最短路c->d->e一定是c到e的最短路，反过来，如果说一条最短路必须要经过点k，那么i->k的最短路加上k->j的最短路一定是i->j 经过k的最短路，因此，最优子结构可以保证。

无后效性

f[k] 的状态完全由f[k-1]转移过来，只要我们把k放倒最外层循环中，就能保证无后效性

为什么只需要二维数组

只与上一层有关，故可缩短置2层
更新点i,j与待跟新点m,n存在关系，只当i,j=n,k或i,j=k,m这两种情况下，本次其实并未更新i，j（j=k或i=k），故可省略此层，动态转移方程可视为f[i][j]=min(f[i][j], f[i][k]+f[k][j])

步骤

三层循环，k放外层，注意i=j时为0

代码实现

https://www.luogu.com.cn/problem/P1629 （其实是双向Dijkstra，所有代码都过不了的~只是找个题目而已qwq）

import java.util.*;

/**
 * @author FHC
 */
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int m = s.nextInt();
        int[][] a = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    a[i][j] = 0;
                } else {
                    a[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            int a1 = s.nextInt();
            int a2 = s.nextInt();
            int a3 = s.nextInt();
            a[a1][a2] = Math.min(a[a1][a2], a3);
        }
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                if (a[i][k] != Integer.MAX_VALUE) {
                    for (int j = 1; j <= n; j++) {
                        if (a[k][j] != Integer.MAX_VALUE) {
                            a[i][j] = Math.min(a[i][j], a[i][k] + a[k][j]);
                        }
                    }
                }
            }
        }
        int sum = 0;
        for (int i = 2; i <= n; i++) {
            sum = sum + a[1][i] + a[i][1];
        }
        System.out.print(sum);
    }
}

概览

单源最短路算法

Dijkstra

原理

步骤

代码实现

链式前向星

Bellman-Ford

原理

步骤

代码实现

SPFA

原理

步骤

代码实现

多源最短路

Floyd

原理

最优子结构

无后效性

为什么只需要二维数组

步骤

代码实现

JAVA final 详解

分布式事务 MySQL与Redis 未完成

354968588