Java节点遍历算法——狄克斯特拉算法（权重算法）

一、简介

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。狄克斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

狄克斯特拉算法解决了有向图最短路径的问题。

二、实现思路

狄克斯特拉算法的实现大致可分为四个步骤：

1. 找出有向图中最便宜的节点

2.更新节点的邻居，判断有没有到下一个节点开销更少的路径

3.如果有就更新该节点的开销及其父节点

4.如果没有，则判断之后还有没有其他相邻的节点，有则继续第一步操作，否则返回结果

以下图为例

Java节点遍历算法——狄克斯特拉算法（权重算法）

要实现查找上图节点中开销最小的路径我们还需要三个散列表(记录节点状态)和一个集合(记录已经处理过的节点)

Java节点遍历算法——狄克斯特拉算法（权重算法）

记录所有节点的开销与邻居记录当前节点的开销信息记录当前节点的父子关系

Java节点遍历算法——狄克斯特拉算法（权重算法）

记录所有已经处理过的节点

三、实现代码

    // 记录所有已经处理过的节点
    private static List<String> fileNode = new ArrayList<>();

    public static void main(String[] args) {

        Map<String,Map<String,Integer>> parent = new HashMap<>();
        Map<String,Integer> node = new HashMap<>();
        node.put("A",6);
        node.put("B",2);
        parent.put("start",node);
        HashMap<String, Integer> mapA = new HashMap<>();
        mapA.put("end",1);
        parent.put("A",mapA);
        HashMap<String, Integer> mapB = new HashMap<>();
        mapB.put("end",5);
        mapB.put("A",3);
        parent.put("B",mapB);
        parent.put("end",new HashMap<>());


        Map<String,String> toFinal = new HashMap<>();
        toFinal.put("A","start");
        toFinal.put("B","start");
        toFinal.put("end","none");

        Map<String,Integer> costs = new HashMap<>();
        costs.put("A",6);
        costs.put("B",2);
        costs.put("end",Integer.MAX_VALUE);

        Map<String, String> method = method(parent,toFinal,costs);
        Set<String> set = method.keySet();
        for (String key : set) {
            System.out.println(key+":"+method.get(key));
        }
    }

    public static Map<String,String> method( Map<String,Map<String,Integer>> totalNode,Map<String,String> toFinal,Map<String,Integer> costs){

        // 找出最便宜的节点
        String lowestNode = getLowestNode(costs);

        // 判断当前节点是否为终点
        while (!"end".equals(lowestNode)){
            // 如果当前节点不是终点 则获取当前节点的开销
            Integer nodeNum = costs.get(lowestNode);
            // 获取当前节点所有邻居
            Map<String, Integer> lowesNodes = totalNode.get(lowestNode);
            Set<String> nodes = lowesNodes.keySet();
            for (String node : nodes) {
                // 计算前往当前节点路径的总开销
                Integer newNum = nodeNum + lowesNodes.get(node);
                // 判断前往节点的开销，找出开销少的节点
                if (costs.get(node) > newNum){
                    // 更新当前节点的开销
                    costs.put(node,newNum);
                    // 更新当前节点的父节点
                    toFinal.put(node,lowestNode);
                }

            }
            // 将已经处理过的节点添加到记录板
            fileNode.add(lowestNode);
            // 找出最便宜的节点
            lowestNode = getLowestNode(costs);
        }

        // 返回结果
        return toFinal;
    }

    // 找出未处理且最便宜的节点
    public static String getLowestNode(Map<String,Integer> costs){
        String lowestNode = null;
        Integer lowest = Integer.MAX_VALUE;
        if (costs != null){
            Set<String> keySet = costs.keySet();
            for (String nodeKey : keySet) {
                Integer num = costs.get(nodeKey);
                if (num < lowest && !fileNode.contains(nodeKey)) {
                    lowest = num;
                    lowestNode = nodeKey;
                }
            }
        }
        return lowestNode;
    }

Java节点遍历算法——狄克斯特拉算法（权重算法）

一、简介

二、实现思路

三、实现代码

相关推荐