黄老师 说的老长了，如果给我们讲个故事 听得会更有趣。
记得 《大话数据结构》里面有说到 广度优先和深度优先算法里，作者 用找东西的例子，广度优先是 到各个地方 比如每个房价 扫一眼，如果没有 再慢慢深入到角落，深度优先 就是 因为有个大概记忆，然后 跟随 记忆 从一个房间 比如抽屉开始 寻找，没有 再去最有可能的角落 找寻，所以 广度优先是 把所有的地方快速扫一眼，没有再慢慢进入小范围 区域，深度优先 就是去指定位置 寻找。
本篇的 Dikstra 大概可以理解：把计算好的节点放入黑箱里，有新的节点加入 只需要与 箱子 的节点连接，然后把新节点与箱子中临近的节点连接起来，计算新节点与临近节点的距离，更新最值，已有的节点间的距离不需要重复计算，总之 Dikstra算法 是没有重复的计算，所以效率会很高，总的计算量会少很多，不像深度优先算法 有大量重复的计算，广度优先算法在添加新节点 时 也会更新已有的计算。
所以Dijstra模块化的思想很节能，它包括 1.寻找MW的最小值或者最大值;2.update更新新节点时，再计算MW的最值。

回答老师的问题：问题一，权限值可以为正为负，例子：跑车游戏中，获胜方为规定时间内奔跑的路程最多，规则为 路线中有不同 奖励，其中有多增加时间的道路，也有减少跑车时间的路线，就是权限值 有正有负。
问题二：多条优先路线，照样可以运用Dijkstra算法，把 多条路线 同时与接入 新节点，然后计算距离，算出MW的值。

有个问题 请教老师：一般地图搜索场景使用Dijkstra多一点还是 动态规划多一点，还是其他算法，地图可以用 百度地图、Google地图 举例。

老师 在专栏里 会谈到 机器学习算法 在生活和产品中的运用吗?

# python 实现
https://github.com/qinggeouye/GeekTime/blob/master/MathematicProgrammer/15_theShortestPath/lesson15_1.py

# 实现效果
用户 0 的好友: [5],     权重值 [0.42]
用户 1 的好友: [4, 9, 0, 6, 3],     权重值 [0.99, 0.16, 0.2, 0.6, 0.1]
用户 2 的好友: 不存在
用户 3 的好友: 不存在
用户 4 的好友: [2, 5, 3],     权重值 [0.17, 0.03, 0.03]
用户 5 的好友: [7],     权重值 [0.19]
用户 6 的好友: [4],     权重值 [0.38]
用户 7 的好友: [8, 1],     权重值 [0.86, 0.63]
用户 8 的好友: [7, 3],     权重值 [0.8, 0.19]
用户 9 的好友: [1],     权重值 [0.97]

------------- Dijkstra 单源最短路径算法 --------------
各下标节点对应的前驱节点： [1, None, 4, 1, 6, 0, 1, 5, 7, 1]
------------- 源点 1 到其它各节点的最短路径 ----------
源点 1 到 0 的最短路径：1 -> 0
源点 1 到 1 的最短路径：不存在
源点 1 到 2 的最短路径：1 -> 6 -> 4 -> 2
源点 1 到 3 的最短路径：1 -> 3
源点 1 到 4 的最短路径：1 -> 6 -> 4
源点 1 到 5 的最短路径：1 -> 0 -> 5
源点 1 到 6 的最短路径：1 -> 6
源点 1 到 7 的最短路径：1 -> 0 -> 5 -> 7
源点 1 到 8 的最短路径：1 -> 0 -> 5 -> 7 -> 8
源点 1 到 9 的最短路径：1 -> 9

思考题1：
如果边的权重是负数，运用Dijksta算法得到是任意两个点之间的最大距离，因为负数比较时，绝对值越大则其值越小，因此算法运行后，两个点之间距离的绝对值是这两个点的最大距离。

思考题2：
存在多条路径情况下，算法修改如下：
(1)增加一个一维数组，path，存贮从源点到各个节点的最优路径数，path[i]，即表示从源点S到节点i的最优路径数，除源节点path[s]=1外，其余各个节点的路径数都初始化为0。
(2)每当新加入一个节点i，则path[i]的值加1。
(3)每当新加入一个节点i，除了更新权重数组MW，还要对F集合中的节点进行检查，对于F中的某个节点k，如果有mw[i] + mw[i,k] = mw[k]，则说明从源点S到节点k至少存在着两条最优权重的路径，因此path[k]也要加1

最后path数组中即为源点到各节点的最优路径数。

a=node('a',{'b':0.2,'c':0.3})
b=node('b',{'d':0.2,'f':0.3})
c=node('c',{'d':0.4,'e':0.1})
d=node('d',{'e':0.3})
e=node('e',{'f':0.2})
f=node('f',{})
mw={}
lastMw={}
nolist={'a':a,'b':b,'c':c,'d':d,'e':e,'f':f}
def getLastNode(mw,lastMw):
    last=min(mw, key=mw.get)
    print('获取到mw最小值',last)
    lastMw[last]=mw[last]

    for k,v in nolist[last].son.items():
        newMw=v+mw[last]
        if k in mw:
            if newMw<mw[k]:
                mw[k]=newMw
        else:
            mw[k] = newMw
    mw.pop(last)

    if mw:
        getLastNode(mw,lastMw)
    return lastMw
acc=getLastNode(a.son,lastMw)
print(acc)
结果输出：
获取到mw最小值 b
获取到mw最小值 c
获取到mw最小值 d
获取到mw最小值 e
获取到mw最小值 f
{'b': 0.2, 'c': 0.3, 'd': 0.4, 'e': 0.4, 'f': 0.5}

// 执行测试
    public static void main(String[] args) {
        Node tree = init();
        Map<String, Double> mw = new HashMap<>();
        Map<String, Double> result_mw = new HashMap<>();

        List<Node> children = tree.children;
        Map<String, Double> weights = tree.weights;
        for (Map.Entry<String, Double> entry : weights.entrySet()) {
            mw.put(entry.getKey(), entry.getValue());
        }

        while (mw.size() != 0) {
            String label = findGeoWithMinWeight(mw);
            updateWeight(label, mw.get(label), result_mw);
            Node min = getMinNode(children, label);
            System.out.println("获取最小值：" + label);
            List<Node> nodes = min.children;
            if (nodes != null && nodes.size() > 0) {
                children.addAll(nodes);
                for (Node node : nodes) {
                    mw.put(node.label, BigDecimal.valueOf(result_mw.get(label))
                            .add(BigDecimal.valueOf(min.weights.get(node.label))).doubleValue());
                }
            }
            mw.remove(label);
        }

        System.out.println(result_mw);
    }
}

运行结果如下：
获取最小值：c
获取最小值：b
获取最小值：d
获取最小值：f
获取最小值：a
获取最小值：c
获取最小值：f
获取最小值：e
获取最小值：g
获取最小值：h
获取最小值：g
{a=0.5, b=0.3, c=0.2, d=0.4, e=0.5, f=0.4, g=0.6, h=0.6}

children = new ArrayList<>();
        children.add(e);
        children.add(h);
        weights = new HashMap<>();
        weights.put("e", 0.1);
        weights.put("h", 0.2);
        f.children = children;
        f.weights = weights;

        children = new ArrayList<>();
        children.add(g);
        weights = new HashMap<>();
        weights.put("g", 0.4);
        h.children = children;
        h.weights = weights;

        return start;
    }

children = new ArrayList<>();
        children.add(e);
        children.add(h);
        weights = new HashMap<>();
        weights.put("e", 0.1);
        weights.put("h", 0.2);
        f.children = children;
        f.weights = weights;

        children = new ArrayList<>();
        children.add(g);
        weights = new HashMap<>();
        weights.put("g", 0.4);
        h.children = children;
        h.weights = weights;

        return start;
    }

    // 获取最小权重
    public static String findGeoWithMinWeight(Map<String, Double> mw) {
        double min = Double.MAX_VALUE;
        String label = "";
        for (Map.Entry<String, Double> entry : mw.entrySet()) {
            if (entry.getValue() < min) {
                min = entry.getValue();
                label = entry.getKey();
            }
        }
        return label;
    }

    // 更新权重
    public static void updateWeight(String key, Double value, Map<String, Double> result_mw) {
        if (result_mw.containsKey(key)) {
            if (value < result_mw.get(key)) {
                result_mw.put(key, value);
            }
        } else {
            result_mw.put(key, value);
        }
    }

    // 获取最小节点
    public static Node getMinNode(List<Node> l, String label) {
        for (Node node : l) {
            if (label.equals(node.label)) {
                return node;
            }
        }
        return null;
    }

1.思考题，如果权重为负数，Dijkstra算法的方式就不能用了。您在文中也提到了，每次取到最小的mw，如果后面出现负数，那前面的权重就不能保证最小了。如果存在多条最优路径，则应该加一个字段记录节点从开始到结束的轨迹。如果权重有多个最优解，则运行轨迹才是需要求解的结果，而不是权重。

2.我将您讲解的推导过程用代码实现了，为了避免小数位数计算导致的精度问题，先转为BigDecimal，再转成了double.由于留言区字数限制，我分开进行提交。
public class Lesson15 {

    // 定义节点
    static class Node {
        public String label;
        public List<Node> children;
        public Map<String, Double> weights;

        public Node(String label) {
            this.label = label;
        }
    }

    // 初始化
    public static Node init() {
        Node start = new Node("s");
        Node a = new Node("a");
        Node b = new Node("b");
        Node c = new Node("c");
        Node d = new Node("d");
        Node e = new Node("e");
        Node f = new Node("f");
        Node g = new Node("g");
        Node h = new Node("h");

        List<Node> children = new ArrayList<>();
        children.add(a);
        children.add(b);
        children.add(c);
        children.add(d);
        Map<String, Double> weights = new HashMap<>();
        weights.put("a", 0.5);
        weights.put("b", 0.3);
        weights.put("c", 0.2);
        weights.put("d", 0.4);
        start.children = children;
        start.weights = weights;

        children = new ArrayList<>();
        children.add(e);
        weights = new HashMap<>();
        weights.put("e", 0.3);
        a.children = children;
        a.weights = weights;

        children = new ArrayList<>();
        children.add(a);
        children.add(f);
        weights = new HashMap<>();
        weights.put("a", 0.2);
        weights.put("f", 0.1);
        b.children = children;
        b.weights = weights;

        children = new ArrayList<>();
        children.add(f);
        children.add(h);
        weights = new HashMap<>();
        weights.put("f", 0.4);
        weights.put("h", 0.8);
        c.children = children;
        c.weights = weights;

        children = new ArrayList<>();
        children.add(c);
        children.add(h);
        weights = new HashMap<>();
        weights.put("c", 0.1);
        weights.put("h", 0.6);
        d.children = children;
        d.weights = weights;

        children = new ArrayList<>();
        children.add(g);
        weights = new HashMap<>();
        weights.put("g", 0.1);
        e.children = children;
        e.weights = weights;