//单源最短路径,bellman_ford算法,邻接表形式,复杂度O(nm)
//求出源s到所有点的最短路经,传入图的大小n和邻接表list
//返回到各点最短距离mind[]和路径pre[],pre[i]记录s到i路径上i的父结点,pre[s]=-1
//可更改路权类型,路权可为负,若图包含负环则求解失败,返回0
//优化:先删去负边使用dijkstra求出上界,加速迭代过程
const int MAXN = 200;
const int INF = 1000000000;
typedef int elemType;
struct Edge {
int from, to;
elemType len;
Edge * next;
};
bool bellmanFord(int n, const Edge * list[], int s, elemType * mind, int * pre) {
int v[MAXN], i, j, k, tag;
const Edge * t;
elemType len;
for (i = 0; i < n; i++) {
mind[i] = INF;
v[i] = 0;
pre[i] = -1;
}
for (mind[s] = 0, j = 0; j < n; j++) {
for (k = -1, i = 0; i < n; i++) {
if (!v[i] && (k == -1 || mind[i] < mind[k])) {
k = i;
}
}
for (v[k] = 1, t = list[k]; t; t = t->next) {
if (!v[i = t->to] && (len = t->len) >= 0 && mind[k] + len < mind[i]) {
mind[i] = mind[pre[i] = k] + len;
}
}
}
for (tag = 1, j = 0; tag && j <= n; j++) {
for (tag = k = 0; k < n; k++) {
for (t = list[k]; t; t = t->next) {
if (mind[k] + (len = t->len) < mind[i = t->to]) {
mind[i] = mind[pre[i] = k] + len;
tag = 1;
}
}
}
}
return j <= n;
}
#include <vector>
using namespace std;
const int MAXN = 200;
const int INF = 1000000000;
template <class elemType>
bool bellmanFord(int n, const vector<pair<int, elemType> > list[], int s, elemType * mind, int * pre) {
int v[MAXN], i, j, k, t, tag;
elemType len;
for (i = 0; i<n; i++) {
mind[i] = INF;
v[i] = 0;
pre[i] = -1;
}
for (mind[s] = 0, j = 0; j<n; j++) {
for (k = -1, i = 0; i<n; i++) {
if (!v[i] && (k == -1 || mind[i]<mind[k])) {
k = i;
}
}
for (v[k] = 1, i = 0; i < list[k].size(); i++) {
if (!v[t = list[k][i].first] && (len = list[k][i].second) >= 0 && mind[k] + len < mind[t]) {
mind[t] = mind[pre[t] = k] + len;
}
}
}
for (tag = 1, j = 0; tag && j <= n; j++) {
for (tag = k = 0; k < n; k++) {
for (i = 0; i < list[k].size(); i++) {
if (mind[k] + (len = list[k][i].second) < mind[t = list[k][i].first]) {
mind[t] = mind[pre[t] = k] + len;
tag = 1;
}
}
}
}
return j <= n;
}
评论0