【数据结构】【算法】Dijkstra算法 最短路 Java实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【数据结构】【算法】Dijkstra算法 最短路 Java实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1866字，纯文字阅读大概需要3分钟。

内容图文

import java.util.*;

public class Main {

    public static void main(String[] args){
        //起点
        String start = "A";
        //建立图
        HashMap<String, List<Node>> map = new HashMap<>();
        map.put("A", Arrays.asList(new Node("B", 5), new Node("C", 1)));
        map.put("B", Arrays.asList(new Node("A", 5), new Node("C", 2),new Node("D",1)));
        map.put("C", Arrays.asList(new Node("A", 1), new Node("B", 2),new Node("D",4),new Node("E",8)));
        map.put("D", Arrays.asList(new Node("B", 1), new Node("C", 4),new Node("E",3),new Node("F",6)));
        map.put("E", Arrays.asList(new Node("D", 3), new Node("C", 8)));
        map.put("F", Arrays.asList(new Node("D", 6)));
        //存放起点到各点的最短路径
        HashMap<String, Node> res = new HashMap<>();
        //优先队列，将去入队的节点按其dis字段从小到大的排列
        PriorityQueue<Node> queue = new PriorityQueue<>();
        //起点 距离自身的距离为0
        Node startNode = new Node(start, 0);
        //将起点入队
        queue.add(startNode);
        //BFS
        while (!queue.isEmpty()) {
            //出队 出队的不一定是距离最短的
            Node cur = queue.poll();
            //添加进入res的一定是最短路径，如果出现重复添加，一定不是最短路径，故舍弃
            if (!res.containsKey(cur.name)) {
                //将距离最短的路径添加进res
                res.put(cur.name, cur);
                //与该节点相邻的节点们
                List<Node> nodes = map.get(cur.name);
                //遍历
                for (Node node : nodes) {
                    //不重复计算已经计算过的节点
                    if (res.containsKey(node.name)) continue;
                    //将没有计算过的入队
                    queue.add(node.setDis(cur.dis).setParent(cur.name));
                }
            }
        }
        //打印起点到各点距离
        for (String s:res.keySet()) {
            Node node = res.get(s);
            System.out.println(node.name+":"+node.dis);
        }

    }

    static class Node implements Comparable<Node>{
        String parent;
        String name;
        int dis;

        public Node(String name, int dis) {
            this.name = name;
            this.dis = dis;
        }

        public Node setDis(int dis) {
            this.dis += dis;
            return this;
        }

        public Node setParent(String parent) {
            this.parent = parent;
            return this;
        }

        @Override
        public int compareTo(Node o) {
            return o.dis>dis?-1:1;
        }
    }
}

参考：[Python] BFS和DFS算法（第3讲）—— 从BFS到Dijkstra算法

内容总结

以上是互联网集市为您收集整理的【数据结构】【算法】Dijkstra算法 最短路 Java实现全部内容，希望文章能够帮你解决【数据结构】【算法】Dijkstra算法 最短路 Java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---