最短路径问题

最短路径问题的抽象

*在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。

这条路径就是两点之间的最短路径（shortest path）

第一个顶点为源点（source）

最后一个顶点为终点（destination）

问题分类

单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径。

       （有向）无权图

       （有向）有权图

多源最短路径问题：求任意两顶点间的最短路径

无权图的单源最短路径算法

按照递增（非递减）的顺序找出到各个顶点的最短路。

void Unweighted ( Vertex S ) 
{ Enqueue(S, Q);
  while(!IsEmpty(Q)){
    V = Dequeue(Q); 
    for ( V 的每个邻接点 W )
      if ( dist[W] == -1  ) {
        dist[W] = dist[V]+1;
        path[W] = V;
        Enqueue(W, Q);
      }
  }
}
           

时间复杂度：T=O(V+E)

有权图的单源最短路算法

按照递增的顺序找出到各个顶点的最短路

Dijkstra算法

dist[w]=min{dist[w],dist[v]+<v,w>的权重}
           

伪代码实现：

void Dijkstra( Vertex s )
{ while (1) {
    V = 未收录顶点中dist最小者;
    if ( 这样的V不存在 )
      break; 
    collected[V] = true;
    for ( V 的每个邻接点 W )
      if ( collected[W] == false ) 
    if ( dist[V]+E<V,W> < dist[W] ) {
         dist[W] = dist[V] + E<V,W> ;
         path[W] = V;
    }
  }
}
           

推荐资料： Dijkstra算法

多源最短路算法

Floyd算法

推荐查看此博客：

最短路径Floyd算法