MENU

求最短路径(迪杰特斯拉算法)

• December 23, 2020 • Read: 31 • 贪心

原题链接

问题描述

在带权有向图G中,给定一个源点v,求从v到G中的其余各顶点的最短路径问题,叫做单源点的最短路径问题。
在常用的单源点最短路径算法中,迪杰斯特拉算法是最为常用的一种,是一种按照路径长度递增的次序产生最短路径的算法。

在本题中,读入一个无向图的带权邻接矩阵(即数组表示),求出源点至每一个其它顶点的最短路径长度。

输入

输入的第一行包含1个正整数n表示图中共有n个顶点,其中n不超过50。
输入的第二行包含一个大写字母M(M – A < n)
以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数,如果大于0,则表示第i个顶点有指向第j个顶点的有向边,且权值为对应的整数值;如果这个整数为10000,则表示没有i指向j的有向边。当i和j相等的时候,保证对应的整数为10000。

输出

共n – 1行
每一行表示源点到其余各点的最短路径长度


解法:贪心思想

Idea

(1)用两个集合S 和 U
S:表示已经求出最短路径的顶点以及相应的最短路径长度
U:表示未求出最短路径的顶点以及该顶点到源点的长度
(2)记录下上一个已经找到的最短路径上的顶点,用pre表示
(3)更新U中的value值,用U中每个顶点到源点的距离 和 与上一个找到的顶点的距离 + 上一个顶点到源点的最短距离,取最小值
(4)找到U中到源点距离最小的那个顶点min
(5)将min添加到S中去,并且将min从U中删除
(6)循环(3)-(5),直到U中没有顶点时结束
(7)S中存储的就是到各个顶点的最短距离

以无向图为例模拟过程

代码

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 有向图找最短路径
 */
public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入顶点个数
        int n = scanner.nextInt();
        // 输入起始顶点
        int V0 = scanner.nextInt();
        int[][] arr = new int[n][n];
        // 输入邻接矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int num = scanner.nextInt();
                arr[i][j] = num == 0 ? 10000 : num;
            }
        }
        // 迪杰斯特拉算法,求出到其余顶点的最短距离
        Map<Integer, Integer> result = dijkstra(arr, V0);
        // 输出结果
        for (int i = 0; i < n; i++) {
            if(i != V0){
                if(result.get(i) == 10000){
                    System.out.print(-1 + " ");
                }else {
                    System.out.print(result.get(i) + " ");
                }
            }
        }
    }

    /**
     * 迪杰斯特拉算法
     * @param arr 邻接矩阵
     * @param V0 起始顶点
     * @return 返回到各个顶点的单源最短路径长度
     */
    private static Map<Integer, Integer> dijkstra(int[][] arr, int V0) {
        int n = arr.length;
        // 存储已求出最短路径的顶点,以及相应的最短路径长度
        Map<Integer, Integer> S = new HashMap<>();
        // 存储还未求出最短路径的顶点,以及该顶点到起点的距离
        Map<Integer, Integer> U = new HashMap<>();
        // 将起点放入S
        S.put(V0, 10000);
        // 将剩余的点放入U
        for (int i = 0; i < n; i++) {
            if(i != V0){
                U.put(i, getDistence(arr, V0, i));
            }
        }
        // 上一个找到的顶点
        int pre = V0;
        // 每次循环找到剩余顶点中的最小值
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n; j++) {
                if(U.get(j) != null){
                    // 比较从当前点到起点的距离 和 当前点到上一个找到的点距离+上一个点到起点的距离
                    int min = Math.min(U.get(j), S.get(pre) + getDistence(arr, pre, j));
                    U.put(j, min);
                }
            }
            // 从U中删除最小距离,添加到S中
            pre = deleteAndAddMin(U, S, n);
        }
        return S;
    }

    /**
     * 将U中距离起点最短的顶点增加到S中,并从U中删除
     * @param u
     * @param s
     * @return 顶点编号
     */
    private static Integer deleteAndAddMin(Map<Integer, Integer> u, Map<Integer, Integer> s, int n) {
        int minIndex = 0;
        // 找到第一个不为空的下标
        while (u.get(minIndex) == null){
            minIndex ++;
        }
        int min = u.get(minIndex);
        // 找到U中的最短那个距离
        for (int i = 0; i < n; i++) {
            if(u.get(i) != null){
                if(u.get(minIndex) > u.get(i)){
                    minIndex = i;
                    min = u.get(i);
                }
            }
        }
        // 将最短那个距离添加到S中,并从U中删除
        s.put(minIndex, min);
        u.remove(minIndex);
        return minIndex;
    }

    /**

     * 获取两个顶点的距离
     * @param arr
     * @param v0
     * @param i
     * @return
     */
    private static Integer getDistence(int[][] arr, int v0, int i) {
        return  arr[v0][i];
    }

}

提交结果

下面给出无向图的解法:

import java.util.*;

/**
 * 单源最短路径问题
 * 如果两个点之间不连通,则设置边的值为10000
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入顶点个数
        int n = scanner.nextInt();
        // 吸收换行符
        String s = scanner.nextLine();
        // 输入起始顶点
        int V0 = (int)(scanner.nextLine().charAt(0) - 'A');
        int[][] arr = new int[n][n];
        // 输入邻接矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = scanner.nextInt();
            }
        }
        // 迪杰斯特拉算法,求出到其余顶点的最短距离
        Map<Integer, Integer> result = dijkstra(arr, V0);
        // 输出结果
        for (int i = 0; i < n; i++) {
            if(i != V0){
                System.out.println("从 " + (char)(V0 + 'A') + " 顶点到 " + (char)(i + 'A') + " 顶点的最短距离为:" + result.get(i));
            }
        }
    }

    /**
     * 迪杰斯特拉算法
     * @param arr 邻接矩阵
     * @param V0 起始顶点
     * @return 返回到各个顶点的单源最短路径长度
     */
    private static Map<Integer, Integer> dijkstra(int[][] arr, int V0) {
        int n = arr.length;
        // 存储已求出最短路径的顶点,以及相应的最短路径长度
        Map<Integer, Integer> S = new HashMap<>();
        // 存储还未求出最短路径的顶点,以及该顶点到起点的距离
        Map<Integer, Integer> U = new HashMap<>();
        // 将起点放入S
        S.put(V0, 10000);
        // 将剩余的点放入U
        for (int i = 0; i < n; i++) {
            if(i != V0){
                U.put(i, getDistence(arr, V0, i));
            }
        }
        // 上一个找到的顶点
        int pre = V0;
        // 每次循环找到剩余顶点中的最小值
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n; j++) {
                if(U.get(j) != null){
                    // 比较从当前点到起点的距离 和 当前点到上一个找到的点距离+上一个点到起点的距离
                    int min = Math.min(U.get(j), S.get(pre) + getDistence(arr, pre, j));
                    U.put(j, min);
                }
            }
            // 从U中删除最小距离,添加到S中
            pre = deleteAndAddMin(U, S, n);
        }
        return S;
    }

    /**
     * 将U中距离起点最短的顶点增加到S中,并从U中删除
     * @param u
     * @param s
     * @return 顶点编号
     */
    private static Integer deleteAndAddMin(Map<Integer, Integer> u, Map<Integer, Integer> s, int n) {
        int minIndex = 0;
        // 找到第一个不为空的下标
        while (u.get(minIndex) == null){
            minIndex ++;
        }
        int min = u.get(minIndex);
        // 找到U中的最短那个距离
        for (int i = 0; i < n; i++) {
            if(u.get(i) != null){
                if(u.get(minIndex) > u.get(i)){
                    minIndex = i;
                    min = u.get(i);
                }
            }
        }
        // 将最短那个距离添加到S中,并从U中删除
        s.put(minIndex, min);
        u.remove(minIndex);
        return minIndex;
    }


    /* 获取两个顶点的距离 */
    private static Integer getDistence(int[][] arr, int v0, int i) {
        return  arr[v0][i];
    }
}

运行结果




作者:喻航

本文标题:求最短路径(迪杰特斯拉算法)

本文链接:https://onedawn.cn/greed/156.html

版权声明:如无特别声明,本文即为原创文章,仅代表个人观点,版权归 雾满拦江 所有,未经允许不得转载!
Archives Tip
QR Code for this page
Tipping QR Code