分类:
单源最短路径算法。

适用于:
稀疏图(侧重于对边的处理)。

优点:
可以求出存在负边权情况下的最短路径。

缺点:
无法解决存在负权回路的情况。

时间复杂度:
O(NE),N是顶点数,E是边数。(因为和边有关,所以不适于稠密图)

算法思想:
很简单。一开始认为起点是“标记点”(dis[1] = 0),每一次都枚举所有的边,必然会有一些边,连接着“未标记的点”和“已标记的点”。因此每次都能用所有的“已标记的点”去修改所有的“未标记的点”,每次循环也必然会有至少一个“未标记的点”变为“已标记的点”。算法实现:

初始化:dis[s] = 0; dis[v] = oo(v != s); pre[s] = 0;

(伪代码)
for(int i = 1; i <= n - 1; i++)
  for(int j = 1; j <= E; j++)  //注意要枚举所有边,不能枚举点
    if(dis[u] + w[j] < dis[v])  //u, v分别是这条边连接的两个点
      {
        dis[v] = dis[u] + w[j]
        pre[v] = u;
      }


---------------------