数据结构：最短路径算法之Bellman-Ford算法

╰+哭是因爲堅強的太久メ 2022-05-31 12:56 188阅读 0赞

# Bellman-Ford算法 #

Bellman - ford算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。

**注意本算法是可以处理负边的**

# 代码如下 #

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    
    const int MAX = 1000000;
    //BellmanFord算法是一个单源最短路径算法,和dijkstra算分有点像,但是该算法可以处理包含
    //负权重的最短路径处理
    
    /*
    6 个节点
    1000000 1000000 10 100000 30 100
    1000000 1000000 5 1000000 1000000 1000000
    1000000 1000000 1000000 50 1000000 1000000
    1000000 1000000 1000000 1000000 1000000 10
    1000000 1000000 1000000 20 1000000 60
    1000000 1000000 1000000 1000000 1000000 1000000
    
    结果
    D[0]   D[1]   D[2]   D[3]   D[4]   D[5]
    0   1000000   10     50     30     60
    
    //节点0到节点5的最短路径是0 4 3 5
    */
    
    
    void BellmanFord()
    {
        const int n = 6;
        int mat[6][6] =
        {
            1000000, 1000000, 10, 100000, 30, 100,
            1000000, 1000000, 5, 1000000, 1000000, 1000000,
            1000000, 1000000, 1000000, 50, 1000000, 1000000,
            1000000, 1000000, 1000000, 1000000, 1000000, 10,
            1000000, 1000000, 1000000, 20, 1000000, 60,
            1000000, 1000000, 1000000, 1000000, 1000000, 1000000 };
    
        int dis[n] = { 0 };
        int pre[n] = { 0 };
    
        //初始化部分
        for (int i = 0; i<n; i++)
        {
            dis[i] = (i == 0) ? 0 : MAX;
            pre[i] = -1;
        }
    
        //节点数量为n,所以做n-1次循环
        for (int i = 1; i<n; i++)
        {
            //这个是针对每一条表做松弛
            for (int j = 0; j<n; j++)
            {
                for (int k = 0; k<n; k++)
                {
                    if (mat[j][k]<MAX)
                    {
                        if (dis[k] > dis[j] + mat[j][k])
                        {
                            dis[k] = dis[j] + mat[j][k];
                            pre[k] = j;
                        }
                    }
                }
            }
        }
    
        //判定是否有回路,无解
        int flag = 1;
        for (int j = 0; j<n; j++)
        {
            for (int k = 0; k<n; k++)
            {
                if (mat[j][k]<MAX)
                {
                    if (dis[k] > dis[j] + mat[j][k])
                    {
                        flag = 0;
                        break;
                    }
                }
            }
            if (flag == 0)
                break;
        }
    
        if (flag == 0)
            cout << "存在回路" << endl;
        else
        {
            //这个就和dijkstra算法很像
            for (int i = 0; i<n; i++)
                cout << dis[i] << "  ";
            cout << endl;
    
            int b = n - 1;
            while (b != -1)
            {
                cout << b << "  ";
                b = pre[b];
            }
        }
    
    }
    int main()
    {
        BellmanFord();
        system("pause");
    }