图的最短路径算法

130 阅读 0 评论 86 点赞

我是靠谱客的博主明亮小天鹅，这篇文章主要介绍图的最短路径算法，现在分享给大家，希望可以做个参考。

最短路径问题的抽象

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

这条路径就是两点之间的最短路径（Shortest Path）
第一个顶点为源点（Source）
最后一个顶点为终点（Destination）

最短路径问题，其实不是一个问题，而是一套问题，这一套问题至少可以分为两大类：

单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径。
- 无权图
- 有权图
多源最短路径问题：求任意两顶点间的最短路径。

.
.
.

无权图的单源最短路算法

按照递增的顺序找出到各个顶点的最短路
将BFS搜索算法修改成为无权图单源最短路算法，其中dist[ W ]表示S到W的最短距离。由于dist[] 初始化时可以设置为一个特别的数，所以dist[ W ]还可以用来标识W是否已被访问过。Path[ W ],S到W的路上经过的某顶点

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void BFS ( Vertex V ) {
    visited[ V ] = true;
    Enqueue( V, Q );
    while ( !IsEmpty( Q ) ){
        V = Dequeue( Q );
        for ( V的每个邻接点W ){
            if ( !visited[ W ] ){
                visited[ W ] = true;
                Enqueue( W, Q );
            }
        }
    }
}

修改为：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
 void Unweighted( Vertex S ){
      Enqueue( S, Q );
      while ( !IsEmpty( Q ) ){
          V = Dequeue( Q );
          for ( V的每个邻接点W ){
              if( dist[ W ] == -1 ){ //如果W被访问过，dist[W]显然不可能为-1
                  dist[ W ] = dist[ V ] + 1;
                  path[ W ] = V;
                  Enqueue( W, Q );
             }
          }
      }
  }