java 实现 dijkstra 算法-- 最优路径

朴灿烈づ我的快乐病毒、 2024-03-17 22:54 156阅读 0赞

### 问题 ###

求出任意一点出发, 到指定点的最短距离和路径  
![在这里插入图片描述][9715f9c6deff4f809d9083d2d4bf1f7c.png]

### 算法代码 ###

//假设起点为src, 终点为dst, 图以二维矩阵的形式存储，若graph[i][j] == 0, 代表i,j不相连
    //visit[i] == 0,代表未访问,visit[i] == -1代表已访问
    public static Node dijkstra(int src, int dst, int[][] graph,int[] visit){
        //节点个数
        int n = graph.length;
        PriorityQueue<Node> pq = new PriorityQueue<>(new Node());
        //将起点加入pq
        ArrayList<Integer> way = new ArrayList<>();
        way.add(src); // 起点路径
        pq.add(new Node(src, 0, way));
        while (!pq.isEmpty()){
            Node t = pq.poll();
            //当前节点是终点，即可返回最短路径
            if(t.node == dst)
                //return t.cost;
                return t;
            //t节点表示还未访问
            if (visit[t.node]==0){
                //将节点设置为已访问
                visit[t.node] = -1;
                //将当前节点相连且未访问的节点遍历
                for (int i = 0; i < n; i++) {
                	// 连通 并且 未被访问
                    if (graph[t.node][i]!=0 && visit[i]==0) {
                        int newCost = t.cost + graph[t.node][i];// 新距离
    
                        List<Integer> newWay = new ArrayList<>(t.way);// 新路线
                        newWay.add(i);
    
                        pq.add(new Node(i, newCost,newWay));
                    }
                }
            }
        }
        //return -1;
        return null;
    }
    
    //定义一个存储节点和离起点相应距离的数据结构
    @Data
    static class Node implements Comparator<Node> {
        public int node; // 节点下标
        public int cost; // 起始节点到当前节点的距离
        public List<Integer> way; // 起始节点到当前节点的路径
    
        public Node(){}
    
        public Node(int node, int cost, List<Integer> way){
            this.node = node;
            this.cost = cost;
            this.way = way;
        }
        // 小顶堆: 头部永远是 cost 最小的
        @Override
        public int compare(Node node1, Node node2){
            return node1.cost-node2.cost;
        }
    }

### 测试代码 ###

public static void main(String[] args) {
      
        // 测试 dijkstra 算法
        int[][] graph = new int[6][6];
        initGraph(graph);
        int[] visit = {0,0,0,0,0,0};
    
        //int dist = dijkstra(0, 4, graph, visit);
        Node node = dijkstra(1, 5, graph, visit);
    
        System.out.println(node);
    }
    
    private static void initGraph(int[][] graph) {
        // 初始图的默认值为0,表示都不相连
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph.length; j++) {
                graph[i][j] = 0;
            }
        }
    
        // 设置连接关系
        graph[0][1] = 7;
        graph[0][2] = 9;
        graph[0][5] = 14;
    
        graph[1][0] = 7;
        graph[1][2] = 10;
        graph[1][3] = 15;
    
        graph[2][0] = 9;
        graph[2][1] = 10;
        graph[2][3] = 11;
        graph[2][5] = 2;
    
        graph[3][1] = 15;
        graph[3][2] = 11;
        graph[3][4] = 6;
    
        graph[4][3] = 6;
        graph[4][5] = 9;
    
        graph[5][0] = 14;
        graph[5][2] = 2;
        graph[5][4] = 9;
    
    }

### 测试结果 ###

点1 到点5的 最短距离为12, 路径为 1,2,5  
![在这里插入图片描述][bc87001c62924433af24f9acc3994544.png]

[9715f9c6deff4f809d9083d2d4bf1f7c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/55dea43bb22e48599bd984dad6935ebd.png
[bc87001c62924433af24f9acc3994544.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/02337de8d8e0447b9f2ecd863d13ea9b.png