迪杰斯特拉算法

迪杰斯特拉算法

之前在进行最短路径计算时使用了广度优先算法，但是找出的只是换乘最少的路径，每次所用的时间其实是不一样的，如果要找出用时最短的路径，可以使用迪杰斯特拉算法(Dijkstra)

如上述路线，从A到D，如果使用广度优先算法的话会得到A->B->D，花费7分钟。而其实最短时间是A->C->B->D，花费6分钟。

迪杰斯特拉算法包含四个步骤

• 找出可在最短时间内到达的节点，站在A点，不知道该前往B点还是C点时，此时由于还不知道前往终点需要多长时间，假设是无穷大。此时C点是最近的

• 第一步算出来C点是距离起点最近的，这一步需要计算出经过C点到其他各邻居节点所需的时间

  A->C->B 需要5分钟

  A->C->D需要8分钟

  OK。此时找到了一条前往B的更短路径。直接前往B需要6分钟，经C之后前往B只需要5分钟。

  所以更新一下到各节点的时间开销

  • 前往B点的路径时间从6分钟缩短到了5分钟
  • 前往终点的时间从无穷大缩短到了8分钟

• 重复前两步操作。重复第一步时排除掉第一次选出的C点，所以选出的点是B点。重复第二步更新B点所有邻居节点的开销。

  此时发现达到终点的时间变为了6分钟。

• 最终算出到达终点的最短时间

使用的是贪心算法

在迪杰斯特拉算法中，给每段都分配了一个权重，找到的是总权重最小的路径

举个栗子

计算A到G的总权重最小路径

public class Dijkstra {

    // 到达所有邻居节点的
    static Map<String, Map<String,Integer>> graphMap = new HashMap<>();
    static {
        Map<String,Integer> aNeighborMap = new HashMap<>();
        graphMap.put("A",aNeighborMap);
        aNeighborMap.put("B",6);
        aNeighborMap.put("C",3);

        // C到达所有邻居节点的
        Map<String,Integer> cNeighborMap = new HashMap<>();
        graphMap.put("C",cNeighborMap);
        cNeighborMap.put("B",2);
        cNeighborMap.put("D",5);

        // B到达所有邻居节点的
        Map<String,Integer> bNeighborMap = new HashMap<>();
        graphMap.put("B",bNeighborMap);
        bNeighborMap.put("D",1);

        // D到达所有邻居节点的
        Map<String,Integer> dNeighborMap = new HashMap<>();
        graphMap.put("D",dNeighborMap);
        dNeighborMap.put("E",3);
        dNeighborMap.put("F",2);

        // E到达所有邻居节点的
        Map<String,Integer> eNeighborMap = new HashMap<>();
        graphMap.put("E",eNeighborMap);
        eNeighborMap.put("G",1);

        // F到达所有邻居节点的
        Map<String,Integer> fNeighborMap = new HashMap<>();
        graphMap.put("F",fNeighborMap);
        fNeighborMap.put("G",3);

    }

    // 到达节点的开销
    static Map<String,Integer> costMap = new HashMap<>();
    static {
        costMap.put("A",0);
        costMap.put("D",Integer.MAX_VALUE);
        costMap.put("C",Integer.MAX_VALUE);
        costMap.put("B",Integer.MAX_VALUE);
        costMap.put("E",Integer.MAX_VALUE);
        costMap.put("F",Integer.MAX_VALUE);
        costMap.put("G",Integer.MAX_VALUE);
    }

    // 处理过的节点
    static Set<String> processed = new HashSet<>();
    static {
        processed.add("A");
        processed.add("G");
    }


    // 存储父节点
    static Map<String,String> parentMap = new HashMap<>();

    static String start = "A";

    public static void main(String[] args) {

//        dijkstra();
        // 走完所有节点
        while (!processed.containsAll(graphMap.keySet())){
            dijkstra();
        }

        System.out.println(costMap.get("G"));

        // 所走路径
        String curNode = "G";
        StringBuilder route = new StringBuilder(curNode);

        while (!"A".equals(curNode)){
            route.insert(0,parentMap.get(curNode)+"->");
            curNode = parentMap.get(curNode);
        }

        System.out.println(route.toString());


    }

    private static void dijkstra() {
        String nextLowerNode = findLowerNode(start);
        if("".equals(nextLowerNode)){
            return;
        }

        // 从起点到该节点的花费时间
        Integer cost = costMap.get(nextLowerNode);

        int newCost = 0;
        // 该节点的所有邻居
        Map<String, Integer> allNeighbors = graphMap.get(nextLowerNode);
        for (Map.Entry<String, Integer> entry : allNeighbors.entrySet()) {
            newCost = cost + entry.getValue();
            if (costMap.get(entry.getKey()) > newCost) { // 如果经当前节点前往邻居节点更近，则更新该邻居的开销，
                costMap.put(entry.getKey(), newCost);
                parentMap.put(entry.getKey(), nextLowerNode); // 将该邻居的父节点设置为该节点
            }
        }
        // 该节点已被处理过
        processed.add(nextLowerNode);
    }

    public static String findLowerNode(String startNode){

        // 先找起点的邻居节点
        Map<String, Integer> nextNodes = graphMap.get(startNode);
        if(processed.containsAll(nextNodes.keySet())){ // 起点的邻居节点全都处理完了
            for(Map.Entry<String,Integer> entry : nextNodes.entrySet()){
                return findLowerNode(entry.getKey());

            }

        }else {
            int cost = Integer.MAX_VALUE;

            String nextNode = "";

            for(Map.Entry<String,Integer> entry : nextNodes.entrySet()){
                if(processed.contains(entry.getKey())){
                    continue;
                }
                // 距离该节点的花费
                if(entry.getValue() < cost){
                    cost = entry.getValue();
                    nextNode = entry.getKey();

                }
            }
            // 起点到该点的花费
            int newCost = costMap.get(startNode)+cost;
            if(newCost < costMap.get(nextNode)){
                costMap.put(nextNode,newCost);
                parentMap.put(nextNode,startNode);
            }
            return nextNode;
        }

        return "";
    }
}