Yyc

用户名：EvoYyc

访问量：1692

签　名：

等　　级
排　　名	14647
经　　验	871
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校	西京学院
专　　业

　　自我简介：

TA的其他文章

城市建设-通过kruskal算法生成最小生成树 [Java][超详细注解]
浏览：542

网络寻路-通过DFS(深搜)+邻接表实现 [Java][超详细注解]
浏览：816

文化之旅-采用Dijkstra寻找最短路径 [Java][详细注解]
浏览：255

你可能喜欢

文化之旅-采用Dijkstra寻找最短路径 [Java][详细注解]

　　作者: Yyc　　　　发表时间：2022-02-06 14:04:37 浏览：255　|　评论：0　

原题链接：蓝桥杯算法提高VIP-文化之旅

# 基本思路
首先求最短路径，我们可以有很多种方案，比如Dijkstra、Foloyd、DFS等方法，都是可以的。
但是这题给定了起点和终点，所以不考虑Foloyd（Foloyd也可以找到最短路径）

> Dijkstra更适合用于单源路径（即特定点到任意一点的距离）
Foloyd则适用于多源问题（即任意点到任意点的距离）。

他又要求所有的数据都是从1开始的，所以我们输入的时候默认都-1，方便我们用list和map时的get操作。

## Dijkstra的介绍
Dijkstra的基本思路就是，从任意指定点开始（即起点）。
不断的对该点的`出度(从该点出发的道路)`进行`松弛(Dijkstra的核心思想)`操作。
从该点的所有`出度`不断更新所有出度连接的目的地的距离。
并且找出最小的那一条路，该条路径所连接的目的地则就是下一个进行出度松弛操作的点。
我们找到了下一个需要进行松弛操作的点之后，再对该点的所有点进行松弛操作。并重复上面的工作即可。

## Dijkstra过程：
如下是我自己拟的一组数据，正确的值应该是 6
> 3 3 3 1 3
1 2 3
0 0 0
0 0 0
0 0 0
1 2 5
1 3 10
2 3 1

### Dijstra基本过程：

1. 起点（1）开始，所有的边进行松弛操作，并找出最短的那条。
>此时找到的最短的是 1 - 2 ：5
其他的路径也需要更新 1 - 3 ：10
那么下一个进行出度松弛的点就是 2
此时 2 的最短路径已经找到了，路程就是 5
此时 3 的`当前`最短路径暂时是 10

2. 找到下一个需要松弛的点（2），并对所有出度进行松弛，并找出一条最短的。
>此时找到的最短的是 2 - 3：1
那么下一个进行出度松弛的点就是 3
到达 3 的新的路径也已经找到了，新的路程长度就是 5 + 1 = 6
那么 6 < 10（`步骤1`直接从起点出发走到3的路程长度）。
则此时确定了 1 - 3 的最短路径就是 6

3. 此时由于所有的点都已经被加入到已经找到的集合里面了，循环就结束了。

## 代码实现
```java
package 蓝桥;

import java.util.*;

public class 文化之旅_1533 {

private static final List<Vertex> vertices = new ArrayList<>();

private static final HashMap<Vertex, Integer> selectPaths = new HashMap<>();

// 题目地址：https://www.dotcpp.com/oj/problem1533.html
    // 思路：Dijkstra 算法 —— 等价思考
    // 并且所有的输入数据，都给我 -1（从 0 开始）
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 国家数、文化数量
        int N = scanner.nextInt(), K = scanner.nextInt(),
                // 道路的条数
                M = scanner.nextInt(),
                // 起点和终点
                S = scanner.nextInt() - 1, T = scanner.nextInt() - 1;
        // 国家编号
        int[] country = new int[N];
        int[][] culture = new int[K][K];
        // 输入国家文化
        for (int i = 0; i < N; i++) {
            country[i] = scanner.nextInt() - 1;
            // 对应的一个地点对象放到list里面存起来
            vertices.add(new Vertex());
        }

// 输入文化排斥关系
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < K; j++) {
                culture[i][j] = scanner.nextInt();
            }
        }

// 输入道路
        // 并且判断对应的路，是否可以走，并做好道路的初始化
        // ！！注意：路是双向的！！
        for (int i = 0; i < M; i++) {
            int from = scanner.nextInt() - 1;
            int to = scanner.nextInt() - 1;
            int distance = scanner.nextInt();
            Edge edge1 = new Edge(from, to, distance);
            Edge edge2 = new Edge(to, from, distance);
            // 检查文化是否排斥
            // 出发地国家的文化
            int fromCC = country[from];
            // 目的地国家的文化
            int toCC = country[to];
            // 看看文化排斥看法
            // f对t(的文化)的态度
            int ftManner = culture[fromCC][toCC];
            // t对f(的文化)的态度
            int tfManner = culture[toCC][fromCC];
            // 如果 f 不排斥 t 则 t 可以到 f来
            // 但是 f 不一定能到 t 去
            if (ftManner != 1) {
                vertices.get(to).outEdge.add(edge2);
            }
            // 如果 t 不排斥 f 则 f 可以到 t 去
            // 但是 t 不一定能到 f 去
            if (tfManner != 1) {
                vertices.get(from).outEdge.add(edge1);
            }
        }

// 通过 dijkstra 求出最短路径
        Vertex start = vertices.get(S);
        Vertex end = vertices.get(T);

// 用来记录临时的路径
        HashMap<Vertex, Integer> paths = new HashMap<>();

// 初始化path，并吧起点所连接的所有点都算做到该点的一条路径
        for (Edge edge : start.outEdge) {
            paths.put(vertices.get(edge.to), edge.distance);
        }

// 如果还有边没有被松弛，则不断循环
        while (!paths.isEmpty()) {
            // 寻找出最短的一个边连接的国家以及到这个国家的路程
            Map.Entry<Vertex, Integer> minVertex = findMinEdge(paths);
            // 该最小的边连接的就是已经被选中的国家，即到这个国家的最短路径，已经被确定了
            selectPaths.put(minVertex.getKey(), minVertex.getValue());
            // 记得从path里面删掉这个国家
            paths.remove(minVertex.getKey());

// 松弛该国家所有的出度
            for (Edge edge : minVertex.getKey().outEdge) {
                // 如果这个点已经确定了最短路径，就不需要松弛操作
                if (selectPaths.containsKey(vertices.get(edge.to))) continue;
                // 计算出新的距离
                int newDistance = minVertex.getValue() + edge.distance;
                // 检查是否之前添加过这个边（即是否找到过他的一条未必是最短的，但是是一条通路的路）
                if (!paths.containsKey(vertices.get(edge.to))) {
                    paths.put(vertices.get(edge.to), newDistance);
                    continue;
                }
                // 从路径中找出该点旧的路径长度
                int oldDistance = paths.get(vertices.get(edge.to));
                // 如果新的路径比他小
                if (newDistance < oldDistance) {
                    paths.put(vertices.get(edge.to), newDistance);
                }
            }
        }

// 输出，如果没有在selectPaths里面找到终点，则说明没有到达过终点，此时get会返回null，则输出 -1
        // 否则就输出selectPaths里面对应国家的结果
        System.out.println(selectPaths.get(end) == null ? -1 : selectPaths.get(end));
    }

private static Map.Entry<Vertex, Integer> findMinEdge(HashMap<Vertex, Integer> paths) {
        // 转化为迭代器
        Iterator<Map.Entry<Vertex, Integer>> it = paths.entrySet().iterator();
        // 先找出第一个点，暂时作为最小边连接的目的地
        Map.Entry<Vertex, Integer> minVertex = it.next();
        // 不断的迭代，并造出最短路径所连接的国家（Vertex）
        while (it.hasNext()) {
            Map.Entry<Vertex, Integer> newVertex = it.next();
            // 看看下一个点的路径，是否小于最短路径
            if (newVertex.getValue() < minVertex.getValue()) {
                minVertex = newVertex;
            }
        }
        // 返回找到的最短路径所连接的国家
        return minVertex;
    }

// 国家对象
    private static class Vertex {
        // 出度
        List<Edge> outEdge = new ArrayList<>();
    }

// 道路对象
    private static class Edge {
        int from;
        int to;
        int distance;

public Edge(int from, int to, int distance) {
            this.from = from;
            this.to = to;
            this.distance = distance;
        }
    }
}

```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Yyc

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【数组的距离】（C语言代码）

矩阵转置（C语言代码）

文化之旅-采用Dijkstra寻找最短路径 [Java][详细注解]

评论区

精彩推荐

C二级辅导-进制转换（C语言代码）

P1002 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

【计算两点间的距离】（C语言代码）

1124题解

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

数列问题（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

小九九（C语言代码）

Yyc

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【数组的距离】 （C语言代码）

矩阵转置 （C语言代码）

文化之旅-采用Dijkstra寻找最短路径 [Java][详细注解]

评论区

精彩推荐

C二级辅导-进制转换 （C语言代码）

P1002 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

【计算两点间的距离】 （C语言代码）

1124题解

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

数列问题 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

小九九 （C语言代码）

【数组的距离】（C语言代码）

矩阵转置（C语言代码）

　　评论区

C二级辅导-进制转换（C语言代码）

【计算两点间的距离】（C语言代码）

用筛法求之N内的素数。（C语言代码）

数列问题（C语言代码）

小九九（C语言代码）