【每日算法】基础算法——求有边数限制的最短路（四十六）

题目内容

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。

注意：图中可能存在负权回路。

输入格式

第一行包含三个整数n，m，k。

接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

输出格式

输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离。

如果不存在满足条件的路径，则输出“impossible”。

数据范围

1≤n,k≤500 ,
1≤m≤10000,
任意边长的绝对值不超过10000。

输入样例

3 3 1
1 2 1
2 3 1
1 3 3

输出样例

题解

Bellman-Ford 算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford 算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。

Bellman-Ford 算法采用动态规划（Dynamic Programming）进行设计，实现的时间复杂度为 O(V*E)，其中 V 为顶点数量，E 为边的数量。Dijkstra 算法采用贪心算法（Greedy Algorithm）范式进行设计，普通实现的时间复杂度为 O(V2)，若基于 Fibonacci heap 的最小优先队列实现版本则时间复杂度为 O(E + VlogV)。

Bellman-Ford 算法描述：

1、创建源顶点 v 到图中所有顶点的距离的集合 distSet，为图中的所有顶点指定一个距离值，初始均为 Infinite，源顶点距离为 0；
2、计算最短路径，执行 V - 1 次遍历；
对于图中的每条边：如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d，则更新终点 v 的距离值 d；
3、检测图中是否有负权边形成了环，遍历图中的所有边，计算 u 至 v 的距离，如果对于 v 存在更小的距离，则说明存在环；

伪代码实现：
1 BELLMAN-FORD(G, w, s)
2 INITIALIZE-SINGLE-SOURCE(G, s)
3 for i 1 to |V[G]| - 1
4 do for each edge (u, v) E[G]
5 do RELAX(u, v, w) //松弛操作，即dist[u] = min(dist[u],dist[v] + w)
6 for each edge (u, v) E[G]
7 do if d[v] > d[u] + w(u, v)
8 then return FALSE
9 return TRUE

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010;

int n, m,k;
int dist[N],backup[N];

struct Edge{
    int a, b ,w;
}edges[M];

int bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for(int i = 0;i < k; i++){
        memcpy(backup, dist, sizeof dist);
        for(int j = 0; j < m; j++){
            int a = edges[j].a, b =edges[j].b, w= edges[j].w;
            dist[b] = min(dist[b],backup[a] + w);
            }
    }
    
    if(dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

int main(){
    scanf("%d%d%d",&n, & m, &k);
    for(int i = 0; i < m; i++){
        int a,b,w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a,b,w};
    }
    
    int t = bellman_ford();
    
    if(t == -1) puts("impossible");
    else printf("%d\n",t);
    
    return 0;
}