Dijkstra迪杰斯特拉算法

最短路径算法

思路

个人感觉迪杰斯特拉算法和普利姆(Prime)算法很像都是从已有集合找到最小边开始，向集合内持续添加最小边的节点。首先写出所有节点的直接路径，从已有集合开始算到其他节点的最短距离，将在这一轮中找到的最小距离所在的节点录入集合，循环……

算法示例

以这个为例我们找出节点1到其他所有节点的最短距离

画出整张表格的框架，顶点 2，3，4，5 初始集合为1，第一轮查看1到2，3，4，5的距离分别为10，无穷，无穷，5。找出第一轮的最短距离为 1-5的距离，将5加入集合。之后再也不用关注5，因为已经是最短距离了（不存在经过其他节点更小的情况，可以自行推算）。

第一轮结束后，集合内有1，5两个节点，且5节点不用再关注了，第二轮开始：看刚刚假如的节点5到其他节点的距离再加上1-5的距离，看是否小于左边的距离，小的话就替换，5到2，3，4的距离分别为3，9，2，加上1到5的距离后为：8，14，7都比左边一列小，所以结果都覆写了，再次找到最小距离：1-5-4的距离7，将4假如集合。

循环到所有节点进入集合即可

代码实现

下次实现