最短路径算法

单源最短路径：

1. Dijkstra      复杂度取决于优先队列如何实现，平均是O(v^2)

思路：

S初始为空，所有结点V放入Q

while(Q不空)

     u=Q中取最小（指距离源点距离最小）

     u并入S

    for(u的每个邻接点v)

         relax();        //松驰，能小就小，咱找最短路径嘛

2. Bellman-Ford        O(VE)

思路：

对每条边松驰(n-1)次。

对每条边再进行一次松驰，如果还能再松，则存在负环。

 

所有结点间的最短路径

FloydWarshall            O(n^3)

初始化d[i, j]=w[i, j]

for(k=1..n)

   for(i=1..n)

     for(j=1..n)

         d[i, j]=min{d[i, j], d[i, k] + d[k,j]}