维基百科
function BellmanFord(list vertices, list edges, vertex source) is
// This implementation takes in a graph, represented as
// lists of vertices (represented as integers [0..n-1]) and edges,
// and fills two arrays (distance and predecessor) holding
// the shortest path from the source to each vertex
distance := list of size n
predecessor := list of size n
// Step 1: initialize graph
for each vertex v in vertices do
distance[v] := inf // Initialize the distance to all vertices to infinity
predecessor[v] := null // And having a null predecessor
distance[source] := 0 // The distance from the source to itself is, of course, zero
// Step 2: relax edges repeatedly
repeat |V|−1 times:
for each edge (u, v) with weight w in edges do
if distance[u] + w < distance[v] then
distance[v] := distance[u] + w
predecessor[v] := u
// Step 3: check for negative-weight cycles
for each edge (u, v) with weight w in edges do
if distance[u] + w < distance[v] then
error "Graph contains a negative-weight cycle"
return distance, predecessor
正解
#include <cstring>
#include <iostream>
#include <algorithm>
namespace alg_{
const int inf=0x3f3f3f3f;
const int N=510;
const int M = 10010;
typedef int vertex;
struct edge{ int u,v,w;};
edge edges[M];
int distance[N];//到起点的距离
int lastDist[N];
//vertex predecessor[N];//前驱
void BellmanFord(int vertex_num,
edge* edges,int edge_size,
vertex source,
int k){
memset(distance,0x3f,sizeof distance);
//memset(predecessor,-1,sizeof predecessor);
distance[source]=0;
for(int loopth=0;loopth<k;loopth++){
memcpy(lastDist,distance,sizeof distance);//保证,循环一次只走一步,不会发生递推
for(int i=0;i<edge_size;i++){
edge e_=edges[i];
if(lastDist[e_.u]+e_.w<distance[e_.v]){
distance[e_.v]=lastDist[e_.u]+e_.w;
//predecessor[e_.v]=e_.u;
}
}
}
}
}
using namespace alg_;
int n, m, k;
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edges[i] = {a, b, c};
}
BellmanFord(n,edges,m,1,k);
if (distance[n] > inf/2) puts("impossible");
else printf("%d\n", distance[n]);
return 0;
}
完整的Bellmanford
#include <cstring>
#include <iostream>
#include <algorithm>
namespace alg_{
const int inf=0x3f3f3f3f;
const int N=510;
const int M = 10010;
typedef int vertex;
struct edge{ int u,v,w;};
edge edges[M];
int distance[N];//到起点的距离
int lastDist[N];
vertex predecessor[N];//前驱
void BellmanFord(int vertex_num,
edge* edges,int edge_size,
vertex source=1){
for(int i=1;i<=vertex_num;i++){
distance[i]=inf;
predecessor[i]=-1;
}
distance[source]=0;
for(int loopth=0;loopth<vertex_num;loopth++){
for(int i=0;i<edge_size;i++){
edge e_=edges[i];
if(distance[e_.u]+e_.w<distance[e_.v]){
distance[e_.v]=distance[e_.u]+e_.w;
predecessor[e_.v]=e_.u;
}
}
}
//多走一步,还能减小,包含负环
for(int i=0;i<edge_size;i++){
edge e_=edges[i];
if(distance[e_.u]+e_.w<distance[e_.v]){
printf("Graph contains a negative-weight cycle.\n");
}
}
}
}
using namespace alg_;
int n, m, k;
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edges[i] = {a, b, c};
}
BellmanFord(n,edges,m);
printf("%d\n", distance[n]);
return 0;
}