前言

看了华为2025年四月份的机考题目，有好多道涉及图论，其中Dijkstra算法考核较为频繁，因此通过此篇记录一下。

关于Dijkstra算法的分析逻辑：https://programmercarl.com/kamacoder/0047.参会dijkstra朴素.html#思路

在本站的笔记中有记录到Dijkstra算法的实现：【卡码网-47】参加科学大会

但是今天亲手试了一下华为的机考真题，发现有很多问题，其中最主要的就是节点的值为String类型，我在网上搜了大量的博文，发现它们的示例题目中节点的值均为int类型，这就意味着它们可以通过构造简单的int[][]二维矩阵去维护邻接表，而如果节点的值为String类型显然不可用此方法。

题目

题目描述（2025.04.09华为机考第二题）

大湾区某城市地铁线路非常密集，乘客很难一眼看出选择哪条线路乘型比较合适，为了解决这个问题，地铁公司希望你开发一个程序帮助乘客挑选合适的乘坐线路，使得乘坐时间最短，地铁公司可以提供的数据是各相邻站点之间的乘坐时间。

输入描述

第一行：N，站点总数，3 <= N <= 20.

第二行：乘客的出发和到达站点。

第三行起：相邻站点之间的乘坐时间，每对站点一行，站点名称是单个小写字母，站点名一定包括出发和到达站点，输入保证只有一个唯一解。

结束行：0000

输出描述（有修改）

最小花费

耗时最短的线路

样例1

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
12
a e
a b 2
b c 2
c d 2
d e 2
f b 3
b g 3
g h 2
h i 3
i h 2
h e 3
e k 2
k l 4
0000

输出

1
2
8
a->b->c->d->e

样例2

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
12
f k
a b 2
b c 2
c d 2
d e 2
f b 3
b g 3
g h 2
h i 3
j h 2
h e 3
e k 2
k l 4
0000

输出

1
2
11
f->b->c->d->e->k

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import java.util.*;

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

        // 读取站点总数
        int N = sc.nextInt();

        // 读取乘客的出发和到达站点
        String start = sc.next();
        String end = sc.next();

        // 利用Map集合初始化邻接表
        // Map<String, Map<String, Integer>>泛型说明：<起点, <终点, 相邻节点间的权重>>
        Map<String, Map<String, Integer>> graph = new HashMap<>();

        // 利用Set集合存储节点，用于后续的遍历操作
        Set<String> nodes = new HashSet<>();

        // 读取边信息直到遇到"0000"
        while (true) {
            String p1 = sc.next();
            if(p1.equals("0000")) {
                break;
            }
            String p2 = sc.next();
            int val = sc.nextInt();
            nodes.add(p1);
            nodes.add(p2);

            // putIfAbsent()方法说明：如果指定的键已经存在，则该方法不会执行任何操作（避免将原有的内容覆盖掉）
            graph.putIfAbsent(p1, new HashMap<>());
            graph.get(p1).put(p2, val);
        }

        // 利用Map集合存储从出发点到每个节点的最短距离
        Map<String, Integer> minDist = new HashMap<>();
        for (String node : nodes) {
            minDist.put(node, Integer.MAX_VALUE);  // 初始化：默认所有节点到出发点的距离为Integer.MAX_VALUE
        }
        minDist.put(start, 0);  // 修改：出发点到自身的距离为0

        // 利用Map集合记录节点是否被访问过
        Map<String, Boolean> visited = new HashMap<>();
        for (String node : nodes) {
            visited.put(node, false);
        }

        // 记录路径，用于最后输出
        Map<String, String> parent = new HashMap<>();

        // 最外层循环：遍历所有节点并添加
        int COUNT = N;
        while (COUNT > 0) {  // 遍历所有节点
            int minVal = Integer.MAX_VALUE;  // minVal用于查找距出发点（start）最近的节点
            String curNode = start;  // 记录当前节点，初始值为start

            // 1、选距离出发点最近且未访问过的节点
            for (String node : nodes) {
                // 如果当前节点未被访问，并且距离出发点距离最小，选中当前节点。
                if (!visited.get(node) && minDist.get(node) < minVal) {
                    minVal = minDist.get(node);
                    curNode = node;
                }
            }

            // 2、标记该节点已被访问
            visited.put(curNode, true);

            // 3、更新非访问节点到出发点的距离
            if (graph.containsKey(curNode)) {  // 由于使用Map集合表示graph，因此并不能保证graph中一定包含当前节点
                for (Map.Entry<String, Integer> entry : graph.get(curNode).entrySet()) {
                    String nextNode = entry.getKey();  // 拿到当前节点的下一个节点
                    int val = entry.getValue();  // 拿到当前节点与下一个相邻节点之间的权重
                    // 如果相邻节点未被访问，并且【当前节点到起始点】的最少权重+【当前节点到相邻节点】的权重 小于 原【相邻节点到起始点】的最少权重，则更新【相邻节点到起始点】的最少权重
                    if (!visited.get(nextNode) && minDist.get(curNode) + val < minDist.get(nextNode)) {
                        minDist.put(nextNode, minDist.get(curNode) + val);
                        parent.put(nextNode, curNode);  // 更新parent集合（不能更改顺序！！）
                    }
                }
            }
            COUNT--;
        }

        // 输出结果
        if (minDist.get(end) == Integer.MAX_VALUE) {
            System.out.println(-1); // 不能到达终点
            return;
        } else {
            System.out.println(minDist.get(end)); // 到达终点最短权重和
        }

        // 输出路径
        List<String> path = new ArrayList<>();
        String cur = end;
        while (cur != null && !cur.equals(start)) {
            path.add(0, cur);
            cur = parent.get(cur);
        }
        path.add(0, start);

        // 输出路径
        for (int i = 0; i < path.size(); i++) {
            if (i != path.size() - 1) {
                System.out.print(path.get(i) + "->");
            } else {
                System.out.print(path.get(i));
            }
        }
    }
}

说明：

  • 如果遇到节点值为String类型，可以利用Map集合构造邻接表。泛型说明：<起点, <终点, 相邻节点间的权重>>

  • 因为使用不了矩阵，因此需要利用Set集合存储节点，用于后续的遍历操作。

  • Map中的putIfAbsent()方法说明：如果指定的键已经存在，则该方法不会执行任何操作（避免将原有的内容覆盖掉），相当于以下代码：

    1
    2
    3
    4
    5
    if(graph.containsKey(p1)) {
        // 不做任何操作，以免覆盖原有内容
    } else {
        graph.put(p1, new HashMap<>());
    }

后记

题目来源：https://mp.weixin.qq.com/s/TrBWkqv3GbjDvttrU3Mx4A

额外说明：如果节点数目很少（如本题），可以采用DFS暴力搜索解决。