1、dijkstra朴素版 时间复杂度O(n^2) 适用与稠密图（点少边多）
以t=-1（不为1到n），用t来找到从1开始，未更新的点，之后以t为起点，更新所有t能到的点，因为从1开始，标记的点已是最短路径，后续不能更改已经标记的点，则如果后续有负权边，则不能更改已经确定的点，因此只能用于正权边的图

2、dijkstra堆优化 时间复杂度O(nlongm) 适用稀疏图（点与边）
这朴素版基础上，用小根堆可以更快找到未标记且是最小的点（队头，出队就标记，表示用已经确定）

3、bellman_ford 时间复杂度O(nm) 限制经过的边数
规定经过的边数，设有前一状态数组（backup）用前一个状态更新最新状态,（类似bfs？以前一状态更新，并且限制次数）这样就阻止发生串联反应（其实是更新的全部点，只不过除了backup能达的点外都更新错误，因为是在无穷的基础上运算，而不是在前一状态），确保这个一次更新是是前一状态能达的一边距离，如此k次，是为限制k次，k后若dis[n]是大于一定范围的数则无解（因为所了后面会更新，但是更新是错误的，n不一定是0x3f3f3f但他没有由前一状态更新，他的值是大于数据范围的（比如最大边数*最大长度））由此判断无解

4、spfa 时间复杂度O(m),最坏O(nm)，可用于负权边的图
用队列储存能到达的、且是目前（注意是目前）距离最小的点，因为spfa更新最小距离的点是更新目前状态的，则在后续如果出现负权边的话可以再次更新已经确定状态的点（因为已经确定状态的点在出队的时候已经撤销标记，则变小后可再次入队，更新之前状态），则可用于有负权边的图