簡單介紹Bellman-Ford演算法

定義：
d [ i ] : = 從 s 到 i 的 最 短 距 離 d[i]:=從s到i的最短距離 d[i]:=從s到i的最短距離
初始化：
d [ s ] = 0 , d [ i ] = I N F , i ∈ V d[s]=0,d[i]=INF,i \in V d[s]=0,d[i]=INF,i∈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 ] : = d[i]:= d[i]:=從s到i的最短路已經求出了后，那么對于節點 i i i附近的節點，可以推出附近節點的暫時的最短距離，而對于這個已經算出的 d [ i ] d[i] d[i]就可以不管了，
所以可以對上述概況為兩點：

1. 找到最短距離已經確定的頂點，從它出發更新相鄰頂點的最短距離，
2. 此后不需要再關心(1)中的“最短距離已經確定的點”，

那么怎么找這個“最短距離已經確定的點”？
最開始只有 d [ s ] = 0 d[s]=0 d[s]=0是已經確定的，而在尚未使用過的頂點中，距離 s s 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，下跪了！