最短路问题(Dijkstra算法、Bellman-Ford算法)

1.Dijkstra算法

Dijkstra算法适用于边权为正的情况。它可用于计算正权图上的单源最短路，即从单个源点出发，到所有节点的最短路。该算法同时适用于有向图和无向图。

伪代码如下：

清除所有点的标号
设d[0]=0, 其他d[i]=INF
循环n次 {
   
	在所有未标号结点中，选出d值最小的结点x
	给结点x标记
	对于从x出发的所有边(x,y)，更新d[y] = min{
   d[y], d[x]+w(x,y)}
}

模拟Dijkstra算法:https://www.bilibili.com/video/av36886088
完整算法

memset(v, 0, sizeof(v));
for(int i = 0; i < n; i++) d[i] = (i==0 ? 0 : INF);
for(int i = 0; i < n; i++) {
   
	int x;
	int m = INF;
	for(int y = 0; y < n; y++) if(!v[i] && d[y]<=m) m = d[x=y];
	v[x] = 1;
	for(int y = 0; y < n; y++)//松弛操作（relaxation） 
		if(d[y] > d[x] + w[x][y]) {
   
			d[y] = d[x] + w[x][y];
		}
}

Bellman-Ford 算法

参考紫书p363
和博客：https://www.jianshu.com/p/e6a20905061c

当负权存在时，最短路不一定存在，但还是有办法在最短路存在的情况下把它求出来。
先确认一个事实：如果最短路存在，一定存在一个不含环的最短路（如果包含正环或零环，去掉以后路径不会变长；如果包含负环，则意味着最短路不存在）

既然不含环，最短路最多只经过n-1个结点，可以通过n-1轮松弛操作得到（起点仍然是0）:

for(int i = 0; i < n; i++) d[i] = INF;
d[0] = 0;
for(int k = 0; k < n-1; k++)//迭代n-1次
	for(int i = 0; i < m; i++)//检查每条边
	{
   
		int x = u[i], y = v[i];
		if(d[x] < INF) d[y] = min(d[y], d[x]+w[i]);//松弛
	}