本文共 4027 字，大约阅读时间需要 13 分钟。
THE CODE:
// Bellman-Ford solved by dynamic prgramming.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#define N 100
#define m 10000 //当作正无穷使用
using namespace std;
int find(int i,int t);
void prin();
int n,e,l;
int pre[2][N];
int edge[N][N];
int main()
{
int u,v,length;
cin>>n>>e;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
edge[i][j]=m;
}
}
for(int i=1;i<=n;i++)
{
pre[0][i]=-1;
pre[1][i]=m;
}
pre[0][1]=1; //以1作为源点
pre[1][1]=0;
for(int i=0;i<e;i++)
{
cin>>u>>v>>length;
edge[u][v]=length;
}
for(int k=2;k<=n;k++)
find(e,k);
prin();
system("pause");
return 0;
}
int find(int i,int t)
{
if(pre[0][t]!=-1 && t!=1)
return find(i-1,pre[0][t])+pre[1][t];
else if(t==1)
return 0;
else
{
int M=m;
for(int j=1;j<=n;j++)
{
if(edge[j][t]!=m && find(i-1,j)+edge[j][t]<M)
{
M=find(i-1,j)+edge[j][t];
l=j;
}
}
pre[0][t]=l;
pre[1][t]=edge[l][t];
return find(i-1,l)+edge[l][t];
}
}
void prin()
{
for(int i=2;i<=n;i++)
{
cout<<i<<"<--";
int j=pre[0][i];
while(j!=1)
{
cout<<j<<"<--";
j=pre[0][j];
}
cout<<"1"<<endl;
}
}
d[k][i][j]定义：“只能使用第1号到第k号点作为中间媒介时，点i到点j之间的最短路径长度。”
d [ k ] [ i ] [ j ] = m i n ( d [ k − 1 ] [ i ] [ j ] , d [ k − 1 ] [ i ] [ k ] + d [ k − 1 ] [ k ] [ j ] ) （ k , i , j ∈ [ 1 , n ] ） d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])（k,i,j∈[1,n]） d[k][i][j]=min(d[k−1][i][j],d[k−1][i][k]+d[k−1][k][j])（k,i,j∈[1,n]）
d[k][u]定义：从源点v出发最多经过不构成负权值回路的k条边到达终点u的最短路径的长度
d i s t [ k ] [ u ] = m i n ( d i s t [ k − 1 ] [ u ] , m i n ( d i s t [ k − 1 ] [ j ] + E d g e [ j ] [ u ] ) ) , j = 0 , 1 , . . . , n − 1 ； j ! = u dist[k][u] = min(dist[k-1][u] ,min(dist[k-1][j]+Edge[j][u])),j = 0,1,...,n-1；j!=u dist[k][u]=min(dist[k−1][u],min(dist[k−1][j]+Edge[j][u])),j=0,1,...,n−1；j!=u
#%%
# dist[k][u] = min{ dist[k-1][u] ,min{dist[k-1][j]+Edge[j][u]} },j = 0,1,...,n-1；j!=uimport numpy as np
def Bellman_Ford_original(graph,start): vertex_num = len(graph) edge_num_ = vertex_num-1 list = np.full((edge_num_+1,vertex_num+1),np.inf) # for i in range(1,vertex_num+1): # list[1,i] = graph[start,i-1] list[:,start+1] =0 for k in range(1,edge_num_+1): for u in range(1,vertex_num+1): result = list[k-1,u] for j in range(1,vertex_num+1): if graph[j-1,u-1]>0 and graph[j-1,u-1]<10000 and result > list[k-1,j] + graph[j-1,u-1]: result = list[k-1,j] + graph[j-1,u-1] list[k,u] =result return list[k,1:]def Bellman_Ford(graph,start):
vertex_num = len(graph) edge_num_ = vertex_num-1 list = np.full((vertex_num+1),np.inf) list[start+1] = 0 path =[-1] * vertex_num for i in range(vertex_num): if graph[start,i] < 10000: path[i] = start path[start] = None # for i in range(1,vertex_num+1): # list[i] = graph[start,i-1]for k in range(1,edge_num_+1): flag = True for u in range(1,vertex_num+1): for j in range(1,vertex_num+1): w = graph[j-1,u-1] if w>0 and w <10000 and list[u] > list[j] + w : list[u] = list[j] + w path[u-1] = j-1 flag = False # 提前退出，并检查是否有负回路 if flag == True: for u in range(1,vertex_num+1): for j in range(1,vertex_num+1): if list[u] > list[j] + graph[j-1,u-1] : print "there is a - cycle" break break
return list[1:],path
第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。 第三，遍历途中所有的边（edge(u,v)），判断是否存在这样情况： d(v)>d(u) + w(u,v) 则返回false，表示途中存在从源点可达的权为负的回路。 之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则应为无法收敛而导致不能求出最短路径。转载地址：http://uzuii.baihongyu.com/