数据结构 —— BellmanFord算法

我们今天来看一个算法BellmanFord算法，我们之前的Dijkstra算法只能用来解决正权图的单源最短路径问题。

Bellman-Ford算法是一种用于计算单源最短路径问题的算法，也就是说，它能找出一个图中某个特定顶点到所有其他顶点的最短路径。与Dijkstra算法不同，Bellman-Ford算法可以处理含有负权边的图，但不能处理包含负权环的图（因为从源点到包含负权环的任意点的距离可以无限减小）。

以下是Bellman-Ford算法的基本步骤：

1. 初始化：将源点到自身的距离设为0，源点到其他所有顶点的距离设为无穷大。
2. 放松操作：对图中的每条边进行V-1次放松操作，其中V是顶点的数量。在每次放松操作中，对于每条边(u, v)，如果dist[v] > dist[u] + weight(u, v)，则更新dist[v] = dist[u] + weight(u, v)。其中，dist[v]表示源点到v的当前最短路径长度，weight(u, v)表示边(u, v)的权重。
3. 检测负权环：再进行一次边的放松操作。如果此时仍存在某条边(u, v)满足dist[v] > dist[u] + weight(u, v)，则说明图中存在负权环。

我们先构建一个这样的图：

BellmanFord算法

BellmanFord算法是站在全局的角度来思考问题，如果这条边可以通过另一条边得到一个更小的结果，就更新，基于这样的思想，我们可以暴力循环来解决：

		bool BellmanFord(const V& srci, vector<W>& dest, vector<int>& parentPath)
		{
			//结点转化
			size_t srcIndex = FindSrci(srci);

			parentPath.resize(_vertex.size(), -1);

			dest.resize(_vertex.size(), MAX_W);

			dest[srcIndex] = W();

			for (size_t i = 0; i < _vertex.size(); i++)
			{
				for (size_t j = 0; j < _vertex.size(); j++)
				{
					if (_matrix[i][j] != MAX_W &&
						dest[j] > _matrix[i][j] + dest[i])
					{
						dest[j] = _matrix[i][j] + dest[i];
						parentPath[j] = i;
					}
				}
			}

			return true;
		}

	void TestGraphBellmanFord()
	{
		const char* str = "syztx";
		Graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.AddEdge('s', 't', 6);
		g.AddEdge('s', 'y', 7);
		g.AddEdge('y', 'z', 9);
		g.AddEdge('y', 'x', -3);
		g.AddEdge('z', 's', 2);
		g.AddEdge('z', 'x', 7);
		g.AddEdge('t', 'x', 5);
		g.AddEdge('t', 'y', 8);
		g.AddEdge('t', 'z', -4);
		g.AddEdge('x', 't', -2);
		g.Print();


		vector<int> dist;
		vector<int> parentPath;

		g.BellmanFord('s', dist, parentPath);
		g.PrintShortestPath('s', dist, parentPath);
	}

我们发现路径是对的，但是权值不对：

这是为什么呢？我们把选边过程挑出来：

bool BellmanFord(const V& srci, vector<W>& dest, vector<int>& parentPath)
		{
			//结点转化
			size_t srcIndex = FindSrci(srci);

			parentPath.resize(_vertex.size(), -1);

			dest.resize(_vertex.size(), MAX_W);

			dest[srcIndex] = W();

			cout << "开始选边: " << endl;
			for (size_t i = 0; i < _vertex.size(); i++)
			{
				for (size_t j = 0; j < _vertex.size(); j++)
				{
					
					if (_matrix[i][j] != MAX_W &&
						dest[j] > _matrix[i][j] + dest[i])
					{
						cout << _vertex[i] << "->" << _vertex[j] << ":" << _matrix[i][j]
							<< endl;
						dest[j] = _matrix[i][j] + dest[i];
						parentPath[j] = i;
					}
				}
			}

			return true;
		}

问题就出在这两个地方：

我们之后的结果会对之前的结果有影响，所以我们还有套一层循环来保证我们的每条边都进行了更新：

			for (size_t k = 0; k < _vertex.size(); k++)
			{
				for (size_t i = 0; i < _vertex.size(); i++)
				{
					for (size_t j = 0; j < _vertex.size(); j++)
					{

						if (_matrix[i][j] != MAX_W &&
							dest[j] > _matrix[i][j] + dest[i])
						{
							cout << _vertex[i] << "->" << _vertex[j] << ":" << _matrix[i][j]
								<< endl;
							dest[j] = _matrix[i][j] + dest[i];
							parentPath[j] = i;
						}
					}
				}
			}
			cout << endl;

			return true;
		}

这下权值就是对的，但是在更新过程中有些边是不用更新的，所以我们可以设计一个标志位来提高效率：

		bool BellmanFord(const V& srci, vector<W>& dest, vector<int>& parentPath)
		{
			//结点转化
			size_t srcIndex = FindSrci(srci);

			parentPath.resize(_vertex.size(), -1);

			dest.resize(_vertex.size(), MAX_W);

			dest[srcIndex] = W();

			for (size_t k = 0; k < _vertex.size(); k++)
			{
				bool exchange = false;
				cout << "开始选边: " << endl;
				for (size_t i = 0; i < _vertex.size(); i++)
				{
					for (size_t j = 0; j < _vertex.size(); j++)
					{
						if (_matrix[i][j] != MAX_W &&
							dest[j] > _matrix[i][j] + dest[i])
						{
							cout << _vertex[i] << "->" << _vertex[j] << ":" << _matrix[i][j]
								<< endl;
							dest[j] = _matrix[i][j] + dest[i];
							parentPath[j] = i;

							exchange = true;
						}
					}
				}

				if (exchange == false)
				{
					break;
				}


			}
			cout << endl;

			return true;
		}

检测负权值环

如果这个图中有负权值环就会导致距离可以无限减小：

所以我们的还有能力检测负权值环：

		bool BellmanFord(const V& srci, vector<W>& dest, vector<int>& parentPath)
		{
			//结点转化
			size_t srcIndex = FindSrci(srci);

			parentPath.resize(_vertex.size(), -1);

			dest.resize(_vertex.size(), MAX_W);

			dest[srcIndex] = W();

			for (size_t k = 0; k < _vertex.size(); k++)
			{
				bool exchange = false;
				cout << "开始选边: " << endl;
				for (size_t i = 0; i < _vertex.size(); i++)
				{
					for (size_t j = 0; j < _vertex.size(); j++)
					{
						if (_matrix[i][j] != MAX_W &&
							dest[j] > _matrix[i][j] + dest[i])
						{
							cout << _vertex[i] << "->" << _vertex[j] << ":" << _matrix[i][j]
								<< endl;
							dest[j] = _matrix[i][j] + dest[i];
							parentPath[j] = i;

							exchange = true;
						}
					}
				}

				if (exchange == false)
				{
					break;
				}


			}

			for (size_t i = 0; i < _vertex.size(); ++i)
			{
				for (size_t j = 0; j < _vertex.size(); ++j)
				{
					// 检查有没有负权回路
					if (_matrix[i][j] != MAX_W
						&& dest[i] + _matrix[i][j] < dest[j])
					{
						return false;
					}
				}
			}

			return true;
		}

我们这里举个例子：

	void TestGraphBellmanFord()
	{
		const char* str = "syztx";
		Graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.AddEdge('s', 't', 6);
		g.AddEdge('s', 'y', 7);
		g.AddEdge('y', 'z', 9);
		g.AddEdge('y', 'x', -3);
		g.AddEdge('z', 's', 2);
		g.AddEdge('z', 'x', 7);
		g.AddEdge('t', 'x', 5);
		g.AddEdge('t', 'y', -8); //修改
		g.AddEdge('t', 'z', -4);
		g.AddEdge('x', 't', -2);
		g.AddEdge('y', 's', 1); // 新增
		g.Print();


		vector<int> dist;
		vector<int> parentPath;

		if(g.BellmanFord('s', dist, parentPath))
			g.PrintShortestPath('s', dist, parentPath);
		else
			cout << "存在负权回路" << endl;
	}

BellmanFord和Dijkstra思想上的区别

Bellman-Ford算法和Dijkstra算法在思想上的主要区别在于它们处理最短路径问题的方式以及它们对图中边权重的假设。下面详细解释这两种算法在思想上的差异：

Dijkstra算法的思想

Dijkstra算法基于贪心策略，它维护一个顶点集合S，其中包含了已经确定了从源点到这些顶点的最短路径的所有顶点。算法的核心思想是每次从未确定最短路径的顶点中选取距离源点最近的那个顶点加入集合S，并更新与之相邻的顶点的距离。

1. 初始化：从源点开始，将其距离设为0，其他所有顶点的距离设为无穷大。
2. 迭代过程：每次迭代选择未被访问过的、距离源点最近的顶点u，将u标记为已访问（加入S集合），并尝试通过u更新其所有未访问邻居的距离。如果通过u到达邻居v的总距离小于v当前记录的距离，则更新v的距离。
3. 终止条件：当所有顶点都被访问过，或者当前最小距离的顶点距离为无穷大时，算法结束。

Bellman-Ford算法的思想

Bellman-Ford算法则采用了动态规划的思想，它通过逐步松弛所有的边，来逼近最短路径的正确解。算法的核心是重复执行“松弛”操作，直到不再有路径可以改进为止。

1. 初始化：同样地，从源点开始，将其距离设为0，其他所有顶点的距离设为无穷大。
2. 松弛操作：算法会遍历图中的所有边多次，每次遍历都尝试通过边的两端点更新路径距离。如果通过某条边可以得到更短的路径，就更新这条路径的距离。这个过程会重复V-1次（V为顶点数量），因为在任何无环图中，从源点到任意顶点的最短路径至多包含V-1条边。
3. 负权重循环检测：在进行了V-1轮的松弛操作后，如果再次遍历所有边时还能进一步更新某个顶点的距离，那就意味着图中存在负权重循环。

思想上的对比

• 适应性：Dijkstra算法假设所有边的权重都是非负的，而Bellman-Ford算法可以处理负权重边（只要不存在负权重循环）。
• 效率：Dijkstra算法在处理无负权重边的图时通常比Bellman-Ford算法更高效，尤其是在使用优先队列优化的情况下。
• 动态规划vs贪心策略：Bellman-Ford算法通过重复松弛所有边来逐渐逼近最短路径，体现了动态规划的思想；而Dijkstra算法通过每次选择局部最优解来逐步构建全局最优解，体现了贪心策略。

总体来说，Dijkstra算法和Bellman-Ford算法各自适用于不同的场景，选择哪个算法取决于图的特性和你对时间和空间效率的需求。

附上源码：

bool BellmanFord(const V& srci, vector<W>& dest, vector<int>& parentPath)
{
    // 将源点名称转换为其在顶点列表中的索引
    size_t srcIndex = FindSrci(srci);

    // 初始化parentPath向量，用于存储最短路径上的前驱顶点
    parentPath.resize(_vertex.size(), -1);

    // 初始化dest向量，用于存储源点到各顶点的最短距离
    dest.resize(_vertex.size(), MAX_W); // MAX_W代表无穷大

    // 设置源点到自身的距离为0
    dest[srcIndex] = W(); // W()应为权重类型的默认构造函数，通常为0

    // 开始Bellman-Ford算法的V-1轮松弛操作
    for (size_t k = 0; k < _vertex.size(); k++)
    {
        bool exchange = false; // 用于检测本轮是否有路径更新
        cout << "开始选边: " << endl;
        // 遍历图中所有的边
        for (size_t i = 0; i < _vertex.size(); i++)
        {
            for (size_t j = 0; j < _vertex.size(); j++)
            {
                // 如果边(i, j)存在且通过边(i, j)可以得到更短的路径
                if (_matrix[i][j] != MAX_W && 
                    dest[j] > _matrix[i][j] + dest[i])
                {
                    cout << _vertex[i] << "->" << _vertex[j] << ":" << _matrix[i][j]
                         << endl; // 输出更新的边信息
                    dest[j] = _matrix[i][j] + dest[i]; // 更新dest[j]的值
                    parentPath[j] = i; // 更新parentPath[j]，记录前驱顶点

                    exchange = true; // 标记发生了路径更新
                }
            }
        }

        // 如果一轮迭代中没有发生路径更新，则提前退出循环
        if (exchange == false)
        {
            break;
        }
    }

    // 检查是否存在负权重循环
    for (size_t i = 0; i < _vertex.size(); ++i)
    {
        for (size_t j = 0; j < _vertex.size(); ++j)
        {
            // 如果通过边(i, j)可以进一步缩短路径，说明存在负权重循环
            if (_matrix[i][j] != MAX_W &&
                dest[i] + _matrix[i][j] < dest[j])
            {
                return false;
            }
        }
    }

    // 如果没有发现负权重循环，返回true，表示算法成功
    return true;
}