学习笔记 - 最短路算法介绍
1、floyd算法：
图中一个顶点到另一个顶点的路径认为有两种，第一种是直接连接，即从起始点连接到终点，路径长度为a [ i ] [ j ]；第二种是间接连接，即通过中间点k将两者连接起来,路径长度为a [ i ] [ k ] + a [ k ] [ j ] 。而Floyd算法的任务即是比较这两种路径，选择出长度较短的路径。
2、dijkstra算法：单源最短路径
如题中的边带有负权值，则dijkstra算法并不适用。
3、spfa算法：
spfa算法与bfs算法类似。用dis数组记录源点到有向图上任意一点距离，其中源点到自身距离为0，到其他点距离为INF。将源点入队，并重复以下步骤：
- 队首x出队，并将该点标记为没有访问过，方便下次入队
- 遍历所有以队首为起点的有向边(x,i)，更新dis[i]
- 如果点i不在队列中，则i入队并标记已访问
- 若队列为空，跳出循环；否则执行1
正环、零环、负环
