Java实现最短路径

本文主要是介绍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);
    }
}

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

运行结果：

这篇关于Java实现最短路径的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！