基础数学课9-图
我们之前在介绍树的时候简单说过，树是一种特殊的连通图，而在现实生活中，图无处不在，比如我们需要从A点到B点，这时候我们需要打开导航去进行路径选择。在这时候，地图天然存在，而导航软件为了计算一个最优解，需要考虑之前我们没有介绍的一个东西，即边的权重，不同路线由于红绿灯等因素，权重是不一样的，这需要导航软件进行实时计算得出最优解。
因此在程序领域中，一个经典的问题就是，如何在由权重的图中，让计算机找到最优解。
这里我们从浅入深，先说下基本的思路，再说下经典的Dijkstra算法。
首先最基本的思路，就是利用广度优先遍历，只不过需要注意的事，广度优先遍历到每一个点的时候，需要看这个点是否已经存在了记录，如果已经通过了，那么需要和当前路径计算，哪一个更优。
在之后就是Dijkstra算法。其核心的思想是，通过发现某些最优的通路，从而确保在最后发现最优的路径。
其最主要的流程是，首先设置除了源点的其他店权重为无限大
然后将源点设置为0，然后将源点的相邻的店加入到一个优先队列中，
然后从优先队列中pop最小的点，加入到结果集之中。则这个点的最小路径就确认了。
之后将这个点相邻的点加入到优先队列中，如果已经存在，就尝试更新权重。
这样不断的出优先队列，从而最终构建出一个到所有的点的图。
我们利用数学定理来推断下这个逻辑是正确的
对于任意一点，Dijkstra都可以找到最小权重的通路。
当n=1的时候，这个规律必然可以找到最小的点
当n = k的时候，我们就需要证明其成立。
如果n = k-1的时候成立，那么增加一个结点x，Dijkstra算法可以X找到最小权重通路。
这里我们分为两种情况，即x的入度和出度。
对于出度来说，如果x不在出度的最小权重通路上，那么必然不影响，如果在的话
那么就意味着 mx[x] + w[x,y] <= nw[y]， 可以推导出来 mw[x] <= mx[y]
所以必然可以在之前看出来。
再之后则是入度，这个更加好推测出来，因为在遍历过程中，必然经过m个z结点中一个，所以寻找mw的过程中，必然会将x加入到mw中，最终就可以找到s到x的最优路径。
那么我们最后说下编码的主要
需要注意的是在过程中，需要确保边是有向的，其实是具有权重的
再其次是完成选择最小的mw，和更新相连的点到优先队列中。