图论入门算法理解

1.Dijsktra 算法

​ Dijsktra算法是基于贪心的，从源点开始扩展，将当前已经是最短路的点加入集合中。dist[i]表示源点s到i的距离，那么初始的时候，找距离源点最近的一个点t0,那么dist[t0]必定是s到t0最短的距离，因为不可能通过其他的点转到t0再让t0最短了（这也是为什么Dijsktra不能处理负权边的原因），同理，扩展第二点的时候也是一样，因为 在扩展第二个点的时候，已经用 第一个点 优化了所有其他的点，那么最近的那个点，一定无法 通过剩余的其他的那个点来 优化自己的距离了，也就是说这个点dist[t1]必定是s到t1的最短路径。

2.floyd：

　　每个点而言，剩余的点的两两最短路，要么经过这个点，要么不经过这个点 ，只要看经过它是否能更短。从另一个角度来理解的话,c[i][j][k]表示i,j经过的中间节点最大的点的标号不超过k的最短路，那么dp的 转移方程就是c[i][j][k]=min(c[i][k][k-1]+c[k][j][k-1],c[i][j][k]).

3.Bellman-ford

​ 进行n次按边松弛的操作，之所以是n次，因为每次松弛过程中，都能保证至少一个点获得了最短路，且每个点最多被经过1次，从DP角度来理解的话，d[k][v]=min(d[k-1][v]+e[u][v],d[k-1][v]),其中e[u][v]代表的是边，d[k][v]表示的是k次以内到达v的最短距离。

4.SPFA

　　最差的情况是n*(n-1)*e,每个点被松弛n-1次,dp[i]=min(dp[v]+mp[v][i],dp[i])