Bellman-Ford算法原理及练习 || LeetCode 787

AI&CV/科技人文求知者/好读书，欲求甚解/努力成为顶尖Coder/

一、Bellman-Ford算法原理

参考链接：
https://zh.wikipedia.org/wiki/贝尔曼-福特算法
 【经典算法】Bellman-Ford最短路径算法 - sms0101的专栏 - CSDN博客
 Bellman-Ford 与 SPFA 算法笔记

伪代码：

procedure BellmanFord(list vertices, list edges, vertex source)
   // 该实现读入边和节点的列表，并向两个数组（distance和predecessor）中写入最短路径信息
   // 步骤1：初始化图
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null
   // 步骤2：重复对每一条边进行松弛操作
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u
   // 步骤3：检查负权环
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "图包含了负权环"

Bellman-Ford算法原理简单来说，就是使用全部的边对于起点到其他n-1个点的路径进行松弛,重复n-1次。算法复杂度为O(VE)。

Bellman-Ford算法有什么用呢？和Dijkstra算法作用相同，可以求出图中（网络中）单源最短路径。Dijkstra算法要求所有权值不能为负数，但Bellman-Ford算法可以。

二、实战练习

Cheapest Flights Within K Stops - LeetCode leetcode.com

根据Bellman-Ford算法很容易就写出：

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int>cost(n,1e6);cost[src]=0;
        for(int i=0;i<=k;i++){
            for(auto&e:flights){
                cost[e[1]]=min(cost[e[1]],cost[e[0]]+e[2]);
        return cost[dst]==1e6?-1:cost[dst];
};

但会出错，为什么呢？要注意到转机次数要小于等于k，而对一个点利用所有边进行松弛的时候，会出现利用多条边即多次转机的情况。为了控制转机次数，我们需要稍微调整一下代码：

//bellman-ford
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int>cost(n,1e6);cost[src]=0;///将所有权值设为inf，考虑到取值范围为[1, 10000].设为1e6即可。
        for(int i=0;i<=k;i++){
            vector<int>c(cost);//控制每次大循环最多只会增加一次转机次数
            for(auto&e:flights)