Java实现最短路径

实现思路： 根据B站视频讲解的过程实现，视频链接
代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class 最短路径 {

    HashMap<String, String> parent;
    HashSet<String> bests;
    int[] distance;

    public 最短路径(int len){
        parent = new HashMap<>(); // key: 当前节点，value：从原点到达key的最短路径的前驱节点
        distance = new int[len]; // distance[i]: 原节点到节点i的最短距离
        bests = new HashSet<>(); // 选择过的最优的节点的集合
    }

    public void dijkstra(int[][] weights, String[] nodes, int v){
        // 1. 初始化：源点到自身距离为0，到其他节点距离为无穷大
        for(int i=0;i<nodes.length;i++){
            if(i==v-1)
                this.distance[i] = 0;
            else this.distance[i] = Integer.MAX_VALUE;
        }
        // 不断迭代
        while (true){
            int min = Integer.MAX_VALUE;
            int index = -1;
            // 1. 在未标记的节点中找出从源点到该点最短的路径节点
            for(int i=0;i<this.distance.length;i++){
                if(this.distance[i] < min && !bests.contains(nodes[i])){
                    min = this.distance[i];
                    index = i;
                }
            }
            // 找不到可达的路径了
            if(index == -1){
                break;
            }
            // 将该节点放入bests集合中
            this.bests.add(nodes[index]);
            // 2. 扩展该节点的子节点，计算源点到子节点的距离，若小于原来距离，则更新
            // distance表和parent表
            for(int i=0;i<nodes.length;i++){
                // 找到一个为扩展的子节点
                if(weights[index][i]>0 && !bests.contains(nodes[i])){
                    int new_dis = distance[index] + weights[index][i];
                    // 新距离小于原始距离，更新
                    if(new_dis < distance[i]){
                        distance[i] = new_dis;
                        parent.put(nodes[i], nodes[index]);
                    }
                }
            }
        }
        // 倒叙找到路径
        for(int i=0;i<nodes.length;i++){
            if(i != v-1){
                if(this.distance[i] == Integer.MAX_VALUE){
                    System.out.print(nodes[v-1]+"到"+nodes[i]+"之间没有最短路径");
                }else {
                    ArrayList<String> path = new ArrayList<>();
                    String current = nodes[i];
                    path.add(current);
                    while (current != nodes[v-1]){
                        current = parent.get(current);
                        path.add(current);
                    }
                    for(int j=path.size()-1;j>=0;j--){
                        if(j!=0)
                            System.out.print(path.get(j)+"->");
                        else System.out.print(path.get(j));
                    }
                }
                System.out.println();
            }

        }
    }
    public static void main(String[] args){
        int[][] weight= {{0,-1,10,-1,30,100},{-1,0,5,-1,-1,-1},{-1,-1,0,50,-1,-1},{-1,-1,-1,0,-1,10},
                {-1,-1,-1,20,0,60},{-1,-1,-1,-1,-1,0}};
        String[] str= {"V1","V2","V3","V4","V5","V6"};
        int len=str.length;
        最短路径 p1 = new 最短路径(len);
        p1.dijkstra(weight, str, 6);
    }
}
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

图的表示：
这里将节点跟权重分开表示，字符串数组str存放节点，二维数组weight存放对应的权重，没有通过权重为-1，节点自身权重表示为0。

运行结果：