算法——迪克斯特拉算法

柔光的暖阳◎ 2021-11-06 00:00 403阅读 0赞

**迪克斯特拉算法主要分四个步骤：**

1.  找到“最便宜”的节点（可在最短时间内到达的节点）。
2.  更新该节点的邻居节点的开销。
3.  重复这个过程，直到对图中每个节点都做了。
4.  计算最终路径。

**这个算法的核心理念是：找到图中最便宜的节点，并确保没有到该节点更便宜的路径。 （所以需要注意的是如果你的图包含负权边，就不能用这个算法，因为这会导致已经处理过的节点更新。）**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70][]

**假设我现在有上面的一张图，计算A->F的最小权重。**

**步骤一：**

**从A可以到B,C,F。相应的权重为：**

**步骤二：**

**由步骤一得出由A->B为当前的最便宜节点，然后找到它相邻的节点：**

**由此可以更新A->D和A->E的权重：**

**步骤三：**

**重复这个操作：**

**C->E:**

**更新最短权重：**

**A->F:**

**当前最短权重为：**

**由D->F可以得到65，A->D为18，更新权重表：**

**由E->F可以得到45，A->E为40，更新权重表：**

**步骤4：**

**最后就可以得到它的最小权重路径：A->B->D->F:83**

**代码实现：**

import java.util.*;
    
    class Node {
        String name;
        int val;
        Map<String, Node> map;
    
        public Node(String name, int val) {
            this.name = name;
            this.val = val;
        }
    
        public Node(String name) {
            this.name = name;
            this.val = val;
        }
    
        public Node() {
    
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getVal() {
            return val;
        }
    
        public void setVal(int val) {
            this.val = val;
        }
    
        public Map<String, Node> getMap() {
            return map;
        }
    
        public void setMap(Map<String, Node> map) {
            this.map = map;
        }
    
        public static void main(String[] args) {
            Node A = new Node("A");
    
    
            //构建A
            Map<String, Node> map = new HashMap<>();
            map.put("B", new Node("B", 8));
            map.put("F", new Node("F", 100));
            map.put("C", new Node("C", 10));
            A.setMap(map);
            //构建B
            Node B = A.getMap().get("B");
            map = new HashMap<>();
            map.put("D", new Node("D", 10));
            map.put("E", new Node("E", 70));
            B.setMap(map);
            //构建C
            Node C = A.getMap().get("C");
            map = new HashMap<>();
            map.put("E", new Node("E", 30));
            C.setMap(map);
            //构建D
            Node D = A.getMap().get("B").getMap().get("D");
            map = new HashMap<>();
            map.put("F", new Node("F", 65));
            D.setMap(map);
            //构建BE
            Node BE = A.getMap().get("B").getMap().get("E");
            map = new HashMap<>();
            map.put("F", new Node("F", 45));
            BE.setMap(map);
            //构建CE
            Node CE = A.getMap().get("C").getMap().get("E");
            map = new HashMap<>();
            map.put("F", new Node("F", 45));
            CE.setMap(map);
    
            //记录存值
            Map<String, Integer> DateMap = new HashMap<>();
            //队列
            List<Node> list = new ArrayList<>();
            //获取A节点下的所有节点
            getListNode(list, A);
            //记录A节点下的值（可能A-F就是最短路径）
            int count = list.size();
            //只要列表不为空
            while (list.size() > 0) {
                //每次减一
                --count;
                Node node = list.get(0);
                //获取这个这个节点的子节点
                List<Node> chiNode = new ArrayList<>();
                getListNode(chiNode, node);
                //只记录A到子节点值
                if (DateMap.get("A" + node.getName()) == null && count >= 0) {
                    DateMap.put("A" + node.getName(), node.getVal());
                } else if (count >= 0) {
                    if (DateMap.get("A" + node.getName()) > node.getVal()) {
                        DateMap.put("A" + node.getName(), node.getVal());
                    }
                }
                if (!chiNode.isEmpty()) {
                    for (Node n : chiNode) {
                        if (DateMap.get("A" + n.getName()) != null) {
                            if (DateMap.get("A" + n.getName()) > (DateMap.get("A" + node.getName()) + n.getVal())) {
                                DateMap.put("A" + n.getName(), (DateMap.get("A" + node.getName()) + n.getVal()));
                            }
                        } else {
                            //添加值
                            DateMap.put("A" + n.getName(), DateMap.get("A" + node.getName()) + n.getVal());
                            DateMap.put(node.getName() + n.getName(), n.getVal());
                        }
                    }
                }
                //获取这个节点下的子节点
                getListNode(list, node);
                //删除
                list.remove(0);
            }
            System.out.println(DateMap.get("AF"));
        }
    
        public static void getListNode(List<Node> list, Node node) {
            Map<String, Integer> map = new HashMap<>();
            if (node.getMap() != null) {
                //获取这个节点的所有子节点
                for (String name : node.getMap().keySet()) {
                    map.put(name, node.getMap().get(name).getVal());
                }
                //排序
                List<Map.Entry<String, Integer>> arrayList = new ArrayList<>(map.entrySet());
                Collections.sort(arrayList, new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });
                //添加节点到末尾
                for (Map.Entry<String, Integer> entry : arrayList) {
                    list.add(node.getMap().get(entry.getKey()));
                }
            }
        }
    
    
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 1][]

再来一个图试试：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 2][]

import java.util.*;
    
    class Node {
        String name;
        int val;
        Map<String, Node> map;
    
        public Node(String name, int val) {
            this.name = name;
            this.val = val;
        }
    
        public Node(String name) {
            this.name = name;
            this.val = val;
        }
    
        public Node() {
    
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getVal() {
            return val;
        }
    
        public void setVal(int val) {
            this.val = val;
        }
    
        public Map<String, Node> getMap() {
            return map;
        }
    
        public void setMap(Map<String, Node> map) {
            this.map = map;
        }
    
        public static void main(String[] args) {
            Node A = new Node("A");
    
            //构建A
            Map<String, Node> map = new HashMap<>();
            map.put("B", new Node("B", 10));
            map.put("D", new Node("D", 20));
            map.put("C", new Node("C", 10));
            A.setMap(map);
            //构建B
            Node B = A.getMap().get("B");
            map = new HashMap<>();
            map.put("F", new Node("F", 5));
            map.put("E", new Node("E", 20));
            B.setMap(map);
            //构建C
            Node C = A.getMap().get("C");
            map = new HashMap<>();
            map.put("F", new Node("F", 20));
            C.setMap(map);
            //构建D
            Node D = A.getMap().get("D");
            map = new HashMap<>();
            map.put("E", new Node("E", 30));
            map.put("G", new Node("G", 100));
            D.setMap(map);
    
            //构建BE
            Node BE = A.getMap().get("B").getMap().get("E");
            map = new HashMap<>();
            map.put("G", new Node("G", 50));
            BE.setMap(map);
            //构建BF
            Node BF = A.getMap().get("B").getMap().get("F");
            map = new HashMap<>();
            map.put("G", new Node("G", 20));
            BF.setMap(map);
    
            //构建CF
            Node CF = A.getMap().get("C").getMap().get("F");
            map = new HashMap<>();
            map.put("G", new Node("G", 20));
            CF.setMap(map);
    
            //构建CE
            Node DE = A.getMap().get("D").getMap().get("E");
            map = new HashMap<>();
            map.put("G", new Node("G", 30));
            DE.setMap(map);
    
    
            //记录存值
            Map<String, Integer> DateMap = new HashMap<>();
            //队列
            List<Node> list = new ArrayList<>();
            //获取A节点下的所有节点
            getListNode(list, A);
            //记录A节点下的值（可能A-F就是最短路径）
            int count = list.size();
            //只要列表不为空
            while (list.size() > 0) {
                //每次减一
                --count;
                Node node = list.get(0);
                //获取这个这个节点的子节点
                List<Node> chiNode = new ArrayList<>();
                getListNode(chiNode, node);
                //只记录A到子节点值
                if (DateMap.get("A" + node.getName()) == null && count >= 0) {
                    DateMap.put("A" + node.getName(), node.getVal());
                } else if (count >= 0) {
                    if (DateMap.get("A" + node.getName()) > node.getVal()) {
                        DateMap.put("A" + node.getName(), node.getVal());
                    }
                }
                if (!chiNode.isEmpty()) {
                    for (Node n : chiNode) {
                        if (DateMap.get("A" + n.getName()) != null) {
                            if (DateMap.get("A" + n.getName()) > (DateMap.get("A" + node.getName()) + n.getVal())) {
                                DateMap.put("A" + n.getName(), (DateMap.get("A" + node.getName()) + n.getVal()));
                            }
                        } else {
                            //添加值
                            DateMap.put("A" + n.getName(), DateMap.get("A" + node.getName()) + n.getVal());
                            DateMap.put(node.getName() + n.getName(), n.getVal());
                        }
                    }
                }
                //获取这个节点下的子节点
                getListNode(list, node);
                //删除
                list.remove(0);
            }
            System.out.println(DateMap.get("AG"));
        }
    
        public static void getListNode(List<Node> list, Node node) {
            Map<String, Integer> map = new HashMap<>();
            if (node.getMap() != null) {
                //获取这个节点的所有子节点
                for (String name : node.getMap().keySet()) {
                    map.put(name, node.getMap().get(name).getVal());
                }
                //排序
                List<Map.Entry<String, Integer>> arrayList = new ArrayList<>(map.entrySet());
                Collections.sort(arrayList, new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });
                //添加节点到末尾
                for (Map.Entry<String, Integer> entry : arrayList) {
                    list.add(node.getMap().get(entry.getKey()));
                }
            }
        }
    
    
    }

![20190809192251272.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 3][]

Node A = new Node("A");
    
            //构建A
            Map<String, Node> map = new HashMap<>();
            map.put("B", new Node("B", 5));
            map.put("C", new Node("C", 2));
            A.setMap(map);
            //构建B
            Node B = A.getMap().get("B");
            map = new HashMap<>();
            map.put("D", new Node("D", 4));
            map.put("E", new Node("E", 2));
            B.setMap(map);
            //构建C
            Node C = A.getMap().get("C");
            map = new HashMap<>();
            map.put("E", new Node("E", 7));
            map.put("B", new Node("B", 8));
            C.setMap(map);
    
            //构建BE
            Node BE = A.getMap().get("B").getMap().get("E");
            map = new HashMap<>();
            map.put("F", new Node("F", 1));
            BE.setMap(map);
            Node BD = A.getMap().get("B").getMap().get("D");
            map = new HashMap<>();
            map.put("F", new Node("F", 3));
            map.put("E", new Node("E", 6));
            BD.setMap(map);
            Node BDE = A.getMap().get("B").getMap().get("D").getMap().get("E");
            map = new HashMap<>();
            map.put("F", new Node("F", 1));
            BDE.setMap(map);
    
            //构建CF
            Node CE = A.getMap().get("C").getMap().get("E");
            map = new HashMap<>();
            map.put("F", new Node("F", 1));
            CE.setMap(map);
            Node CB = A.getMap().get("C").getMap().get("B");
            map = new HashMap<>();
            map.put("D", new Node("D", 4));
            map.put("E", new Node("E", 2));
            CB.setMap(map);
            Node CBD = A.getMap().get("C").getMap().get("B").getMap().get("D");
            map = new HashMap<>();
            map.put("F", new Node("F", 3));
            map.put("E", new Node("E", 6));
            CBD.setMap(map);
            Node CBDE = A.getMap().get("C").getMap().get("B").getMap().get("D").getMap().get("E");
            map = new HashMap<>();
            map.put("F", new Node("F", 1));
            CBDE.setMap(map);
            Node CBE = A.getMap().get("C").getMap().get("B").getMap().get("E");
            map = new HashMap<>();
            map.put("F", new Node("F", 1));
            CBE.setMap(map);

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 4][]

OK~迪克斯特拉算法的实现！！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70]: /images/20211104/524f8806edb3488f80d525e4c7f43590.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 1]: /images/20211104/322760acd0994f5993b1e208e3de546c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 2]: /images/20211104/abfdc67a055145c8ac1ffbf66f44e2a4.png
[20190809192251272.png]: /images/20211104/eb2df275615e4e8fba048d0e17b60199.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 3]: /images/20211104/d67a68933d3d4878a3bc7195755a5cdd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 4]: /images/20211104/c04b54f5de1046eb88e207ac341d0330.png