搜索与图论篇——图的最短路

搜索与图论篇——图的最短路

本次我们介绍搜索与图论篇中的图的最短路，我们会从下面几个角度来介绍：

• Dijkstra简介
• Dijkstra代码
• Dijkstra优化
• Floyd简介
• Floyd代码
• Kruskal简介
• Kruskal代码

Dijkstra简介

我们首先来介绍第一种求图的最短路的基本算法：

/*算法前述*/

// 该算法属于较为复杂图的最短路算法,适用于求解一点到该图所有点之间的距离
    
// 只能用来求解边权为正数的情况，默认复杂度为O(n^2),但是后期如果采用队列优化复杂度为O(mlogn)

/*算法概述*/

前置条件：
    
我们需要n个数，m条边
    采用dis记录每个数到原始节点的距离
    采用mdis记录每条边两点之间的距离值
    采用ispassed记录该点是否已经被使用过

该算法主要分为三步：

1.初始化信息：dis均设置正无穷，将dis[0]=0,初始化mdis（手动输入）
    
2.从初始值开始更新dis数据，如果存在mdis与该点有关就进行更新，最后我们选出当前未经过点的最短点，加入ispassed并用它进行下一次遍历
    
3.循环上步操作直到mdis全部使用
    
/*更新判断条件*/
    
dis更新条件：t是当前最短点，x是根据t更新的点，w是两点距离
    
dis[x] ? dis[t] + w;

最短点更新条件：
    
forn时，提前设置一个t=-1，并不断判断，如果t==-1 || dis[t] > dis[x],就将t=x;

Dijkstra代码

我们首先给出Dijkstra的基本代码：

/*代码说明*/

这里我们采用双for的形式进行全部点的遍历，并在每次遍历中进行全部点数据的更新，复杂度为O(n^2)

/*代码展示*/

import java.util.Scanner;

public class Main {

    final static int INF = 510;

    // 准备条件
    static int n,m;
    static int[] dis = new int[INF];
    static int[][] mdis = new int[INF][INF];
    static boolean[] ispassed = new boolean[INF];


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        // 数值初始化
        for (int i = 1; i <= n; i++) {
            dis[i] = INF;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j){
                    mdis[i][j] = 0;
                }else {
                    mdis[i][j] = INF;
                }
            }
        }

        // 初始化(所有边权均为正值)
        for (int i=0;i// a,b为边，c为权重
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();

            // 注意：图中可能存在自环,重边
            mdis[a][b] = Math.min(mdis[a][b],c);
        }

        // 进行Dijkstra算法
        int dijkstraN = dijkstra();

        System.out.println(dijkstraN);
    }

    public static int dijkstra(){
        // 首先第一个值距离改为0
        dis[1] = 0;

        // 开始查找最小值，并开始遍历
        for (int i=0;i < n;i++){
            // t为当前最小值点，并以此更新dis数据
            int t = -1;
            for (int j = 1; j <= n; j++) {
                // 这个点没有经过，且距离最短（或者尚未初始化t时）
                if (!ispassed[j] && (t == -1 || dis[t] > dis[j])){
                    t = j;
                }
            }

            // 设为经过点
            ispassed[t] = true;

            // 得到最短点，并借此更新dis
            for (int k = 1; k <= n; k++) {
                dis[k] = Math.min(dis[t] + mdis[t][k],dis[k]);
            }
        }

        // 最后判断n是否更新成功，若更新成功返回n的dis
        if (dis[n] == INF) return -1;
        return dis[n];
    }
}

Dijkstra优化

我们再给出优化方法：

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    final static int N = 510;

    // 我们这次采用队列和邻接表的形式减少一次for循环
    static int n,m,idx;
    static int [] h = new int[N],e = new int[N],ne = new int[N],w = new int[N];
    static int [] dis = new int[N];
    static boolean[] ispassed = new boolean[N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        // 初始化
        for (int i = 1; i <= n; i++) {
            h[i] = -1;
        }
        
        for (int i = 1; i <= n; i++) {
            dis[i] = N;
        }

        while (m -- > 0){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();

            // 我们采用链表的形式
            add(a,b,c);
        }

        int res = dijkstra();

        System.out.println(res);
    }

    // 链表方法
    public static void add(int a,int b,int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    private static int dijkstra() {
        // 采用优先队列的形式
        PriorityQueue queue = new PriorityQueue();

        dis[1] = 0;

        // 将第一个值加入队列
        queue.add(new PIIs(0,1));

        // 不为空执行
        while (!queue.isEmpty()){
            // 找到第一个为经过点抛出
            PIIs p = queue.poll();
            int distance = p.getFirst();
            int t = p.getSecond();
            if(ispassed[t]) continue;

            // 根据该点更新数据，并将最小值加入queue
            
            ispassed[t] = true;

            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];// i只是个下标，e中在存的是i这个下标对应的点和值。
                if(dis[j] > distance + w[i])
                {
                    dis[j] = distance + w[i];
                    queue.add(new PIIs(dis[j],j));
                }
            }
        }

        // 输出结果
        if(dis[n] == N) return -1;
        return dis[n];
    }

}

// 我们需要一个class类放于queue队列中
class PIIs implements Comparable{
    private int first;//距离值
    private int second;//点编号

    public int getFirst()
    {
        return this.first;
    }
    public int getSecond()
    {
        return this.second;
    }
    public PIIs(int first,int second)
    {
        this.first = first;
        this.second = second;
    }
    @Override
    public int compareTo(PIIs o) {
        // TODO 自动生成的方法存根
        return Integer.compare(first, o.first);
    }
}

Floyd简介

我们来介绍第二种求图的最短路的算法：

/*算法前述*/

// 该算法属于最基础的图的最短路算法,适用于求解当前图中所有点到所有点之间的距离
    
// 该算法可以用于求解负权边，但是无法求解负权回路问题

/*算法概述*/

该算法就是采用最暴力的形式，来源于动态规划
    
我们直接对每个点k，将k作为中间点，对该图中所有点a和所有点b做一个借助k缩短路径的尝试，若尝试成功修改dis，若失败跳过
    
我们给出核心算法：
    for(int k = 1;k <= n;k++){
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                dis[i][j] = Math.min(dis[i][j],dis[i][k] + dis[k][j]);
            }
        }
    }
    
/*更新判断条件*/
    
dis[i][j] = Math.min(dis[i][j],dis[i][k] + dis[k][j]);

Floyd代码

我们给出Floyd算法的基本代码：

import java.util.Scanner;

public class Floyd {

    final static int N = 210;
    final static int MAX = 0x3f3f3f3f;

    // 我们只需要一个mdis装载之间的距离即可
    static int n,m,k;
    static int[][] mdis = new int[N][N];

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();
        k = scanner.nextInt();

        // 初始化
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i==j){
                    mdis[i][j] = 0;
                }else {
                    mdis[i][j] = MAX;
                }
            }
        }

        // 输入值
        while(m -- > 0 ){

            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();

            //这里可能存在重边，取最小的边
            mdis[a][b] = Math.min(mdis[a][b],c);
        }

        // Floyd算法
        floyd();

        // 给出询问点距离
        while(k -- > 0){
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int dis  = mdis[x][y];
            // 这里可能最后到不了目标点，但是可能路径上面存在负权边，然后将目标点更新了，所以不是到底== INF
            if(dis > MAX / 2) System.out.println("impossible");
            else System.out.println(dis);
        }
    }

    // floyd算法
    private static void floyd() {
        // 直接三层循环即可
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    mdis[i][j] = Math.min(mdis[i][j],mdis[i][k] + mdis[k][j]);
                }
            }
        }
    }

}

Kruskal简介

这里我们介绍一种在图中求最小生成数的算法：

/*算法前述*/

// 该算法帮助我们在图中求最小生成树

/*算法概述*/

该算法需要用到两个前置知识点：快速排序和并查集
    
快速排序我们可以采用Java函数来替代，并查集大家可以移步其他文章先行观看，下面我也会简单介绍并查集
    
我们的算法主要分为两步：
    
1.将所有边按照权重大小排序（因为我们需要获得最小生成树=我们的最后树的权重需要是最小的，所以我们从最小权重的边开始进行连接）
    
2.我们从小到大枚举每条边，如果该边的两点没有连接（并查集知识），我们就将他们连接起来，如果已连接我们继续下一条边
    
/*并查集简述*/
    
我们在这儿仅介绍一下并查集思想
    
我们对每个数据都采用一个数字代替
    
例如我们采用p[i] = i，让每个点都指向自己本身
    
当我们需要将两个点连接起来时，我们只需要让a点的i变成b点的i即可（注意：所有使用a点的i都需要更换为b点的i）
    
我们在进行两点相连判断时，只需要找到对应的p[i]查看是否相等即可！

Kruskal代码

我们给出Floyd算法的基本代码：

import java.util.Arrays;
import java.util.Scanner;

public class Kruskal {

    final static int N = 10010;

    // 边集合和并查集集合
    static int n,m;
    static Edgs[] edgs = new Edgs[N];
    static int[] p = new int[N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        // 初始化
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }

        // 边赋值
        for (int i = 1; i <= m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int w = scanner.nextInt();

            edgs[i] = new Edgs(a,b,w);
        }

        // kruskal操作
        kruskal();
    }

    private static void kruskal() {

        // 将结构体中的权重数据从小到大排序好
        Arrays.sort(edgs,1,m+1);

        // 权重之和
        int res = 0;
        // 边数
        int cnt = 0;

        // 枚举所有边
        for (int i = 1; i <= m; i++) {
            // 将该边抽取出来
            Edgs edg = edgs[i];
            int a = edg.a;
            int b = edg.b;
            int w = edg.w;

            // 区块判断
            a = find(a);
            b = find(b);

            // 判断该边两侧点是否属于同一区块
            if (a != b){
                // 不属于同一区块，需要更该区块，权重之和相加，cnt++
                p[a] = b;
                res += w;
                cnt++;
            }
        }
        //因为有n个点，所以有n-1条边，所以如果小于n-1就是存在不连通的边，所以输出impossible，否则输出权重之和res
        if(cnt < n - 1) System.out.println("impossible");
        else System.out.println(res);
    }

    //并查集模板，所有的集合在过程中全部指向根节点
    public static int find(int x){
        if(p[x] != x) p[x] = find(p[x]);
        return  p[x];
    }


}

// 采用class表示边
class Edgs implements Comparable{
    int a,b,w;

    public Edgs(int a,int b,int w){
        this.a = a;
        this.b = b;
        this.w = w;
    }

    public int compareTo(Edgs o){
        return  Integer.compare(w,o.w);
    }
}

结束语

好的，关于搜索与图论篇的图的最短路就介绍到这里，希望能为你带来帮助~