//最短路算法
Dijkstra
朴素版本O(n^2)//使用邻接矩阵
遍历n次
1.每次找出当前离1最近的点 标记为t 将t打上标记 //此时1-t已经是最短距离
2.循环n次 利用t以及t至各点的距离更新每点到1的最短距离
堆优化O(mlogn)//使用邻接表
1.将{0,1}加入堆中 first为至1的距离
2.当堆不空时 每次循环取堆顶 将堆顶的点打上标记 //堆顶一定是堆顶点到1最短的距离(堆代替了朴素版本的第一步)
利用t以及t至各点的距离更新每点到1的当前最短距离,如果更新就入堆
bellman-flod O(nm)//傻瓜做法
1.遍历n次 //n个点最短距离最多走过边数为n-1条 若第n次进行了更新,则存在负权闭环
2.每次遍历m条边,更新最短距离
spfa 一般O(m) 极少数O(nm)
1.将1入队 打上标记 //标记为是否在队中
2.队列不为空时 取出队头 取消标记
遍历队头的所有出边,如果更新了某出度的最短距离且这点不在队中,打上标记并入队
循环往复直至没有点改变最短距离(即没有点在队中)