Dijkstra算法比较快速，但是如果遇到负边就无能为力了，而Bellman算法可以解决负边问题，只要不是负环。
这个算法数据结构没有讲过，他主要是每次对所以边进行松弛操作，进行n-1次得到最短路径。
其原理如下所述：
首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|n-1条边。
其次，从源点s可达的所有顶点如果存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。
在对每条边进行1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1 条边，所以，只需要循环|v|-1 次。
如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从s到v不可达。
如果有负权回路，那么第 |v|-1 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。
根据这个原理写出代码如下：
bool Bellman(int s,int n){ fill(dis,dis+n,inf); dis[s]=0; for(int i=0;i<n-1;i++){//n-1此松弛操作 int flag=1; for(int u=0;u<n;u++) { for(int j=0;j<Adj[u].size();j++) { int x=Adj[u][j].v; if(dis[u]+Adj[u][j].weight<dis[x]) {dis[x]=dis[u]+Adj[u][j].weight;//松弛操作 flag=0; } } } if(flag)return true;//如果这一轮没有被松弛，直接退出 } for(int u=0;u<n;u++) //判断是否存在负环 { for(int j=0;j<Adj[u].size();j++) { int x=Adj[u][j].v; if(dis[u]+Adj[u][j].weight<dis[x]) return false;//还能松弛存在负环，失败 } } return true; }
虽然理解简单但是这个算法耗时较大，每一轮都要遍历所有边，其实由于一个顶点u的d[u]改变时，以此点出发的邻接点d[v]才可能改变，结合Bellman树的形成过程可以类比层次遍历，用一个队列存放结点，每拿出一个结点对邻接点松弛，如果能松弛且不在队列里就让其入队，直到队空（说明无负环，）或者某个结点入队超过n-1次，说明有负环。这就是SPFA算法，一般比Dijkstra算法还要快，比较高效。代码如下：
bool SPFA(int s,int n){ fill(inq,inq+n,false);//记录是否入队 fill(num,num+n,0);//记录入队次数 fill(dis,dis+n,inf); queue<int>q; q.push(s); inq[s]=true; num[s]++; dis[s]=0; while(!q.empty()){ int u=q.front();q.pop(); inq[u]=false; for(int j=0;j<Adj[u].size();j++){ int x=Adj[u][j].v; if(dis[u]+Adj[u][j].weight<dis[x]){ dis[x]=dis[u]+Adj[u][j].weight; if(!inq[x]) { q.push(x); num[x]++; inq[x]=true; if(num[x]>n-1)//负环 return false; } } } } return true; }
此外关于最短路径还有一个Floyd算法，这里打包带走，下面是三个算法的全体代码：
#include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; const int maxv=101; const int inf=10000000; struct node{ int v,weight; }; vector<node>Adj[maxv] ; int dis[101]; //bellman算法 bool Bellman(int s,int n){ fill(dis,dis+n,inf); dis[s]=0; for(int i=0;i<n-1;i++){//n-1此松弛操作 int flag=1; for(int u=0;u<n;u++) { for(int j=0;j<Adj[u].size();j++) { int x=Adj[u][j].v; if(dis[u]+Adj[u][j].weight<dis[x]) {dis[x]=dis[u]+Adj[u][j].weight;//松弛操作 flag=0; } } } if(flag)return true;//如果这一轮没有被松弛，直接退出 } for(int u=0;u<n;u++) //判断是否存在负环 { for(int j=0;j<Adj[u].size();j++) { int x=Adj[u][j].v; if(dis[u]+Adj[u][j].weight<dis[x]) return false;//还能松弛存在负环，失败 } } return true; } //SPFA算法 bool inq[maxv] ; int num[maxv]; bool SPFA(int s,int n){ fill(inq,inq+n,false); fill(num,num+n,0); fill(dis,dis+n,inf); queue<int>q; q.push(s); inq[s]=true; num[s]++; dis[s]=0; while(!q.empty()){ int u=q.front();q.pop(); inq[u]=false; for(int j=0;j<Adj[u].size();j++){ int x=Adj[u][j].v; if(dis[u]+Adj[u][j].weight<dis[x]){ dis[x]=dis[u]+Adj[u][j].weight; if(!inq[x]) { q.push(x); num[x]++; inq[x]=true; if(num[x]>n-1) return false; } } } } return true; } //floyd算法 int d[maxv][maxv] ; void floyd(int n){ for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(d[i][k]!=inf&&d[k][j]!=inf&&d[i][k]+d[k][j]<d[i][j]) d[i][j]=d[i][k]+d[k][j]; } int main(){ int n,m,s,t; int x,y,w; node temp; scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=0;i<m;i++){ scanf("%d%d%d",&x,&y,&w); temp.weight=w; temp.v=x; Adj[y].push_back(temp); temp.v=y; Adj[x].push_back(temp); } if(SPFA(s,n)) { for(int i=0;i<n;i++) printf("%d ",dis[i]); } return 0; }
