最短路讲解【算法竞赛 - 10.8】

· · 算法·理论

最短路算法有很多种，都用于解决图论中两点之间最短路径问题。

板子题传送门->（天立OJ）

最短路问题无非就三种：

  1. 是否需要计算边权
  2. 是否存在负环（图中存在一个环，环上所有边权和为负数）
  3. 单源最短路 / 多源最短路

针对这些类型的最短路问题，就诞生了各类的最短路算法。

一、 Floyd 算法（全称Floyd-Warshall算法）

  1. 特点：容易编码 ，思路简单，能处理多源最短路问题和找出图中的负环

能一次性求得所有节点之间的最短距离，其他的最短路算法做不到。 ——《算法竞赛·下册》

  1. 算法效率： O(n^3)，效率特别慢，能处理图中点数为300以内的数据
  2. 算法空间：由于使用邻接矩阵记录边和记录答案，所以需要n*n的空间，占用很大空间，但在400范围内绝对足够的。

  3. 算法思路：

    • 先初始化所有点之间距离为INF
    • 最外层循环遍历所有中转点k
    • 第二层和第三层循环遍历所有起点和终点i和j
    • 更新起点和终点i和j的最短距离

一阵操作后，就等于尝试了所有点之间的所有走法，自然能得出最短路径。最后邻接矩阵中就得到了所有点之间的最短距离。

5.注意：

  1. 可能存在重边：只存入更短的一条边
  2. 判断负环：如果任意两点之间出现了距离dis[i][j] < 0那么就存在负环
  3. 注意三层循环的顺序，最外层是中转点，里面两层是起点和终点

AC代码

#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn = 1005, INF = 1e9 + 5;

int n, m, s, t, dis[maxn][maxn];
void Init() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i != j) {
                dis[i][j] = INF;
            }
        }
    }
}

void Input() {
    scanf("%d %d %d %d", &n, &m, &s, &t);
    Init();                                                         //注意Init()的位置，否则会影响正常边的存入
    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        dis[u][v] = dis[v][u] = min(dis[u][v], w);                  //解决重边问题，只记录最小的一个边
    }
}

void Floyd() {
    for (int k = 1; k <= n; ++k) {                                  //遍历中转点
        for (int i = 1; i <= n; ++i) {                              //遍历起点
            for (int j = 1; j <= n; ++j) {                          //遍历终点
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);  //更新起点到终点的最短路径
            }
        }
    }
}

void Print() {
    printf("%d", dis[s][t]);
}

int main() {
    Input();
    Floyd();
    Print();
    return 0;
}