原理：

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

來源：

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

流程：

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

鄰接表：

#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;
}