---

简单介绍Bellman-Ford算法

定义：
$$d[i]:=从s到i的最短距离$$
初始化：
$$d[s]=0,d[i]=INF,i\in V$$
利用递推式：
d [ i ] = m i n { d [ j ] + ( 从 j 到 i 的 权 重 ) ∣ e = ( i , j ) ∈ E } d[i]=min\{ d[j]+(从j到i的权重)|e=(i,j)\in E \} d[i]=min{d[j]+(从j到i的权重)∣e=(i,j)∈E}
直到不在更新就完成了

代码：

#include<bits/stdc++.h>

using namespace std;
const int MAX_V=100,MAX_E=100;
const int INF=0x7ffffff;
struct edge{
	int from,to,cost;
};
edge es[MAX_E];
int d[MAX_V];
int V,E;
void shortest_path(int s){
	for(int i=0;i<V;++i) d[i]=INF;
	d[s]=0;
	while(true){
		bool update=false;
		for(int i=0;i<E;++i){
			edge e= es[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(){
    int s;
    cin>>V>>E;
    for(int i=0;i<E::++i){
		int s,e,w;
		cin>>s>>e>>w;
		es[i].from=s;
		es[i].to=e;
		es[i].cost=w;
	}
	cin>>s;
	shortest_path(s);
	for(int i=0;i<V;++i){
		printf("%d->%d的最短路：%d\n",s,i,d[i]);
	}
	return 0;
}

他的优点

对于负圈而言，Bellman-Ford算法能处理负圈。

因为负圈也就是有负权，那么自然对于每次循环自然可以更新，所以就会无限更新。但是我们稍微想一想，如果对于一个没有负圈的图中，我们最坏情况是要更新多少次呢？当然，可以想到是|V|-1次，因为如果存在一个节点i，从s到i必须经过所有节点，所以自然要迭代|V|-1才能更新这个i节点。
所以利用这个性质，我们可以实现检测是否存在负圈。
代码：

bool find_negative_loop(){
	memset(d,0,sizeof d);
	
	for(int i=0;i<V;++i){
		for(int j=0;j<E;++j){
			edge e=es[j];
			if(d[e.to]>d[e.from]+e.cost){
				d[e.to]=d[e.from]+e.cost;
				
				//如果第n次还有更新，则存在负圈
				if(i==V-1) return true;
			}
		}
	}
	return false;
}

他的缺点

每一次更新都需要将所有边遍历一遍，很浪费时间

正如上面代码所看，对于每次迭代，我们必须把所以边都遍历一次，对于可能仅仅需要更新一个边而言，实在是浪费。所以Dijstra算法就可以优化这个问题所以接着看吧。

Dijstra算法思想

根据Bellman-Ford算法的缺点，我们就可以思考：如何可以更高效的更新节点？
其实我们用人的思想可以看得出，如果对于$d[i]:=$从s到i的最短路已经求出了后，那么对于节点$i$附近的节点，可以推出附近节点的暂时的最短距离。而对于这个已经算出的$d[i]$就可以不管了。
所以可以对上述概况为两点：

1. 找到最短距离已经确定的顶点，从它出发更新相邻顶点的最短距离。
2. 此后不需要再关心(1)中的“最短距离已经确定的点”。

那么怎么找这个“最短距离已经确定的点”？
最开始只有$d[s]=0$是已经确定的。而在尚未使用过的顶点中，距离$s$节点最近的顶点就是最短路距离已经确定的顶点。如果存在负圈则会无法确定最小。

代码：

#include<bits/stdc++.h>

using namespace std;
const int INF = 0x7ffffff
const int MAX_V=100;

//cost[u][v]表示边e=(u,v)的权重（不存在就是INF）
int cost[MAX_V][MAX_V];
int d[MAX_V];
bool used[MAX_V];
int V;

void Dijstra(int s){
	fill(d,d+V,INF);
	fill(used,used+V,false);
	d[s]=0;

	while(true){
		int v=-1;
		for(int u=0;u<v;++u){
			//不断更新，找到尚未使用且最短距离的节点
			if(!used[u]&&(v==-1||d[u]<d[v])) v=u;
		}
		
		//没有更新就说明更新完了
		if(v==-1) break;
		used[v]=true;

		for(int u=0;u<V;++u){
			//如果两条节点没有连接就是无穷大，所以就没有更新
			d[u]=min(d[u],d[v]+cost[v][u]);
		}
	}
}

int main(){
	int from,to,cost;
	int s; 
	fill(cost,cost+MAX_V*MAX_V,INF);
	for(int i=0;i<V;++i){
		cost[i][i]=0;
	}
	cin>>s;
	while(cin>>from>>to>>cost){
		cost[from][to]=cost;
	}
	Dijsktra(s);
	for(int i=0;i<V;++i){
		printf("%d->%d的花销：%d\n",s,i,d[i]);
	}
	return 0;
}

优点与缺点

他的缺点

无法处理负圈，对于负圈还是需要用上Bellman-Ford算法

他的优点

处理比Bellman-Ford算法快一点

可以看出，每次去最短点是要遍历一次的，并且更新的时候也需要遍历完所有边。所以他的优点并没有完全体现出来所以就有了下面的优化。

优化

插入（更新）

对于插入，也就是更新操作中，我们可以使用邻接表来优化

取出

对于取出，我们则可以使用堆这个数据结构完成优化，也就是STL中的优先队列priority_queue实现。
那么上代码：

#include<bits/sdtc++.h>
using namespace std;
const int INF = 0x7fffff;
const int MAX_V=100;
typedef pair<int,int> P; //first是最短距离，second是顶点编号
struct edge{ int to,cost; };

int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s){
	//STL的priority_queue本身是取最大值的，所以要加greater<TYPE>。
	priority_queue<P,vector<P>,greater<P>> que;
	fill(d,d+V,INF);
	d[s]=0;
	que.push(0,s);

	while(!que.empty()){
		P p = que.top(); que.pop();
		int v = p.second();
		if(d[V]<p.first) continue;
		for(int i=0;i<G[v].size();++i){
			edge e = G[v][i];
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				que.push({d[e.to],e.to});
			}
		}
	}
}

int main(){
	int from,to,cost;
	int s; 
	cin>>V;
	for(int i=0;i<V;++i){
		int from,e,w;
		cin>>from>>e>>w;
		G[from].push_back({e,w});
	}
	cin>>s;
	
	Dijsktra(s);
	for(int i=0;i<V;++i){
		printf("%d->%d的花销：%d\n",s,i,d[i]);
	}
	return 0;
}

最后感想

花了两节C语言课，才写完，各位爷可以给我这个小博主点个赞吗？
Orz，下跪了！