原理：

• 在有向圖中,對于某個邊(u,v,w),若存在dist[v] < dist[u] w,滿足三角關(guān)系，
• 若所有邊都滿足此不等式,說明一個點已經(jīng)無法通過任意聯(lián)通點來松弛它,則所有的dist就是最短路

來源：

• 與 dij不同的是,bellman-ford基于迭代思想
• spfa是隊列優(yōu)化的bellman-ford

流程：

1. 將源點加入隊列,
2. 取出隊頭,掃描所有出邊(u,v,w),松弛:dist[v] > dist[u] w,若v點不在隊列中,加入隊列
3. 隊列中保存了待擴展的節(jié)點，每一次節(jié)點的入隊都更新了一次dist數(shù)組,一個點可能多次入隊,不斷的迭代

鄰接表：

#include <iostream>
#include <string.h>
#include <queue>
#include <vector>

using namespace std;
const int maxn = 1e3;
const int INF = 0x3f3f3f3f;

queue<int> que;
bool vis[maxn];
int dist[maxn];
int n,m;
vector<pair<int,int> > e[maxn];

void spfa() {
	memset(dist,0x3f,sizeof dist);
	memset(vis,0,sizeof vis);

	dist[1] = 0; vis[1] = 1;
	que.push(1);

	while (!que.empty()) {
		int cur = que.front(); que.pop();
		vis[cur] = 0;
		for (int i=0; i<e[cur].size(); i  ) {
			int to = e[cur][i].first;
			int div = e[cur][i].second;
			if (dist[to] > dist[cur]   div) {
				dist[to] = dist[cur]   div;
				if (!vis[to]) vis[to] = 1,que.push(to);
			}
		}
	}
	return ;
}

void read() {
	memset(e,0x3f,sizeof e);
	scanf("%d%d",&n,&m);
	for (int i=1; i<=m ;i  ) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[u].push_back( make_pair(v,w) );
	}
}

int main() {
	read();
	spfa();
	return 0;
}

鄰接矩陣 HDU 1874

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;
const int maxn = 201;
const int INF = 0x3f3f3f3f;
int e[maxn][maxn];
int startp,endp;
bool vis[maxn];
int dist[maxn];
int n,m;

int spfa() {
	memset(vis,0,sizeof vis);
	memset(dist,0x3f,sizeof dist);

	dist[startp] = 0; vis[startp] = 1;
	queue<int> que;
	que.push(startp);

	while (!que.empty()) {
		int cur = que.front(); que.pop();
		vis[cur] = 0;
		for (int i=0; i<n; i  ) {
			if (e[cur][i] < INF && dist[i] > dist[cur]   e[cur][i]) {
				dist[i] = dist[cur]   e[cur][i];
				if (!vis[i]) que.push(i),vis[i] = 1;
			}
		}
	}
	return dist[endp];
}
int main() {
//	freopen("a.txt","r",stdin);
	while (scanf("%d%d",&n,&m) != EOF) {
		memset(e,0x3f,sizeof e);
		for (int i =1; i<=m; i  ) {
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			if (w < e[u][v]) e[u][v] = e[v][u] = w;
		}
		scanf("%d%d",&startp,&endp);
		int ans = spfa();
		if (ans < INF) printf("%d\n",ans);
		else printf("-1\n");
	}
	return 0;
}