图论-单源最短路径—贝尔曼福特算法Bellman–Ford

定义

贝尔曼-福特算法，求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的。

它的原理是对图进行松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高。

定义

​ 给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径 [1] 问题。

• V是点的集合
• E是边的集合

思路理清

• 材料准备：

  1. 边：edge
     1. 花费（从点i到点j的权值）cost
     2. 起点
     3. 终点
  2. 单源：起点s
  3. 顶点数V
  4. 边数E
  5. 从起点到任意点的最短路径d[]

• 初始化：将d数组全部赋值为INF

• 流程：

  个人理解：这是一个不断打通且不断刷新的过程（一条边的起始端点如果还没有被访问到（或者永远不会被访问到），那么接纳这条边影响的操作是暂时被搁置到一旁的）。

  至于为什么能保证路径是最短的，那是因为每做一遍循环，都要把所有的边重新检查一下，直到无法再更新（这个时候可以设置一个参数update来调停）。

代码实现

#include<iostream>
#include<stdio.h>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef struct{
	int cost,from,to;
}edge;

edge edges[5000];

int d[5000];
int V,E;//V是点集，E是边集 
int s;//单源 

void find_shortestpath(int s)
{
	for(register int i=1;i<=V;i++)
	{
		d[i]=INF;
	}
	d[s]=0;
	bool update;
	while(true)
	{
		update = false;
		for(register int i=0;i<E;i++)
		{
			edge e=edges[i];
			if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost)
			{
			    d[e.to] = d[e.from]+e.cost;
				update=true;
			}
		}
		if(!update)
		    break;
	}
}

int main()
{
	cin>>V>>E>>s;
	for(register int i=0;i<E;i++)
	{
		cin>>edges[i].from>>edges[i].to>>edges[i].cost; 
	}
	find_shortestpath(s);
	for(register int i=1;i<V;i++)
	{
		cout<<d[i]<<" ";
	}
	cout<<d[V];
	return 0;
}

资料

挑战程序设计竞赛