数据结构复习考试（9）

发表于   |  

介绍

最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

算法具体的形式包括：

  • 确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。
  • 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。
    在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
  • 确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。
  • 全局最短路径问题 - 求图中所有的最短路径。

用于解决最短路径问题的算法被称做“最短路径算法”。

单源最短路径

SPFA

算法大致流程 是用一个队列来进行维护。
初始时将源点加入队列，每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队，直到队列为空时算法结束。

SPFA算法（Shortest Path Faster Algorithm），也是求解单源最短路径问题的一种算法，用来解决的问题如下：
给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。

SPFA算法是 Bellman-Ford 算法的一种队列实现，减少了冗余计算，他的基本算法和 Bellman-Ford 一样，并用如下方法改进：

  1. 第一步，不是枚举所有节点，而是通过队列来进行优化，设置一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值 对 离开u点所指向的结点v 进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

  2. 同时，除了通过判断队列是否为空来结束循环，还可以通过下面的方法：即判断有无负环，如果某个点进入队列的次数超过V次，则存在负环（SPFA算法无法处理带负环的图）。

SPFA 在形式上和 BFS（广度优先搜索）非常类似，不同的是：在广度优先搜索中，一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右。

然而在实际的应用中SPFA算法的时间效率不是很稳定，为了避免最坏情况的出现，通常使用时间效率更加稳定的Dijkstra算法。

SPFA模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//gh[][]为有向图（gh[i][j]为结点i到结点j的权值，如果gh[i][j]不存在，则为-1）
//dis[] 中所有元素应初始化为INFINITY(0xfffffff最大值)
//vis[] 中所有元素应初始化为false。
//num[] 记录各结点入队列次数

bool spfa(int s){
    //若 s 为终点，直接返回
    //path[] 用于记录路径
    
    queue<int> Q;
    
    Q.push(s);
    dis[s] = 0;
    
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        vis[u] = true;
        
        for (int v = 1; v <= n; v++) {
            if (dis[v] > dis[u] + gh[u][v]){
                dis[v] = dis[u] + gh[u][v];
                //path[v] = u;
                //num[v]++;
                //if (num[v] > n) return false;    //判断负环
                if (!vis[v]) {
                    vis[v] = true;
                    Q.push(v);
                }
            }
        }
        vis[u] = false; //将出队列的的点置为false
    }
    return true;
}

任意两点最短路径

使用条件&范围：通常可以在任何图中使用，包括有向图、带负权边的图。

Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。

注意单独一条边的路径也不一定是最佳路径。

  • 从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
  • 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
  • 不可思议的是，只要按排适当，就能得到结果。 
1
2
3
4
5
6
7
8
9
10
11
12
// dist(i,j) 为从节点i到节点j的最短距离
for i←1 to n do
   for j←1 to n do
      dist(i,j) = weight(i,j) 
 
for k←1 to n do // k为“媒介节点”
  for i←1 to n do
    if (i<>k) then
      for j←1 to n do
        if (i<>j) && (k<>j) then
          if (dist(i,k) + dist(k,j) < dist(i,j)) then
              dist(i,j) = dist(i,k) + dist(k,j)

Reference

http://www.nocow.cn/index.php/SPFA%E7%AE%97%E6%B3%95s

http://www.nocow.cn/index.php/Floyd-Warshall%E7%AE%97%E6%B3%95