Graph 圖論

最短路（Bellman_Ford）

缺點：不能計算包含負環的圖

前面我們已經學習了dijkstra算法來求最短路，但是dijkstra有一個很大的問題就是無法計算有負權值的圖，這是因為dijkstra找到一個目前dist最小點的時候便将該點設定為已通路，便不再處理該點，這對邊權為非負數的時候适用，因為該點的權值不會再被更新（dijkstra）,然而如果一個圖的邊帶有負權值，那麼該算法便不再适用，因為即使是目前dist最小的點之後還有可能會被負值所更新，是以我們就不能像dijkstra那樣将一個标記為已被通路就不在管他，我們不能對點進行處理了，是以我們換個方式而是對邊進行處理，每一條邊都對應了三個屬性，一個是起點，一個是終點，一個是邊權，是以我們很容易想到用一個結構體來存儲這三種屬性：

struct edge{
	int a,b;
	int cost;
};
edge map[600001];
           

然後我們就是對邊進行處理了，一共我們有m條邊，我們每次循環就要對這m條邊進行周遊，確定我們每次更新dist值都能夠考慮所有的邊對其的影響，這樣的循環最多進行 n-1 次（如果不存在從起點可達的負環，那麼最短路不會經過同一個點兩次，也就是說最多通過v-1條邊，while循環醉倒執行n-1次），我們可以設定一個update來判斷是否目前循環是否有更新dist值，如果進行中某次循環沒有更新dist值，也就是說經過這次循環程式中的任何值都沒有發生變化，是以就可以退出來了，就沒有必要再做剩下的循環了（因為循環下去我們所需要的dist的值也不會再發生變化了）。

循環的主要内容是我們判斷一下目前我們所知的這條邊是否能對dist值進行更新，這個想法跟dijkstra一樣，

if(dist[E.b] > dist[E.a] + E.cost)

=> dist[E.b] = dist[E.a] + E.cost;

完整代碼如下：

#include<iostream>
#include<cstring>
using namespace std;
const long long inf = 0x7f7f7f7f;
struct edge{
	int a,b;
	int cost;
};
edge map[600001];
int n,m;
int dist[100001];
void bellman_ford(int begin){
	memset(dist,inf,sizeof(dist));
	dist[begin] = 0;
	bool update = true;
	while(update){
		update = false;
		for(int i=0;i<m;i++){
			edge E = map[i];
			if(dist[E.b] > dist[E.a] + E.cost){
				update = true;
				dist[E.b] = dist[E.a] + E.cost;
			}
		}
	}
}
int main(){
	int begin;
	cin >> n >> m;
	cin >> begin;
	for(int i=0;i<m;i++){
		cin >> map[i].a >> map[i].b >> map[i].cost;
	}
	bellman_ford(begin);
	for(int i=1;i<=n;i++){
		if(dist[i]==inf) cout << 2147483647 << " ";
		else cout << dist[i] << " ";
	}
	return 0;
}