dijkstra算法呢，还有其它很多的各种变形的应用，
一种是当我们在求最短路径的时候，我们还需要数等长的最短路径一共有多少条，另外一类问题在所有的最短路里面，我要找那个包含的边数最少的最短路，先来看第一种，要数最短路径有多少条，那么很自然的，我们得加一个计数器的数组，我们把它叫作count,那对任意一个结点v,count[v]就记录的是从源点到v的最短路径一共有多少条，那初始化的时候呢，我们就是源点的这个count,要把它设为1，从源点的count等于1开始，我们开始执行dijkstra算法，如果把一个v收到集合里面，使得我们w可以找到一条更短的话，w的count应该怎么样更新呢？
其实因为从V到W就只有一条边，所以从s到V,曾经有多少条最短路，那么从s到W也就会有多少条最短路，你只要把这个数字继承过来就可以了，那下一个问题是说，如果我找到了另外一条等长的最短路，这个时候W又要怎么更新呢？
一个很常见的错误，当我们找到另一条等长路径的时候，我们会让这个count[W]就直接加1，我们以为是找到了另外1条等长路径，但是且慢，你要停下来想一下，当我们这条新的等长路径是从V走到W的时候，从s到V再到W,虽然从V到W只有一条边，但是从s到V这边的最短路可不一定是只有一条，所以V带给W的，不一定是一条路，它可能是一堆等长最短路，那另外一个问题呢，我们要求边数最少的最短路，其实仔细想一下，这个问题跟我们这个旅游规划其实是等价的，旅游规划问题要求的不是边数最少，是边数的费用和最少，但是如果你想想如果把费用全部定义为1，那不就等价为边数最少吗？所以这个问题，其实我们已经解决过了，但是在解决前面旅游规划问题的时候，我少说了一件事情，那就是费用的初始化怎么做？那在这里面呢，我不叫cost,我仍然把它叫做count,就是计数器来数这个边数的，如果我数的是最短路径有多少条，那我在原点的count初始化为1了，我要求的是边数最少最短路的时候，那么原点的这个count应该被初始化什么呢？千万不要把它初始化为1，一定要把它初始化为0，因为从s到s自己是没有边的，接下来的事情就很简单了，我们前面其实也已经讨论过了，如果我找到更短路的时候，这个count应该是什么呢，应该是count[V]+1,那这个1你可以把它理解为一个边的特殊的权重就是1，当这个边有其它权重的时候，这个地方就应该是被换成其它的权重，如果我们找到了另外一条等长路的时候，这个处理方法其实也是一样的。仍然是count[V]加上这条边新的权重。
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/31537575/viewspace-3165750/ ，如需转载，请注明出处，否则将追究法律责任。
