介紹

全稱Bellman-Ford算法，目的是求解有負權邊的最短路徑問題。
考慮環，根據環中邊的邊權之和的正負，將環分為零環、正環、負環。其中零環、正環不會影響最短路徑的求解，而負環會影響最短路徑的求解。
可用BF算法返回一個bool值來判斷是否有負環，如果有返回false,否則返回true.

bool BF(int b){fill(path,path+maxn,INF);path[b]=0;//求最短距離for(int i=0;i<n-1;i++){//比較趟數for(int j=0;j<n;j++){//遍歷每一個頂點相關的鄰接邊for(int k=0;k<table[j].size();k++){int v=table[j][k].v;int value=table[j][k].value;if(path[j]+value<path[v]){//此時path[v]應該是最小距離path[v]=path[j]+value;}}}//判斷是否有負環：有返回false,無返回truefor(int m=0;m<n;m++){//再次遍歷邊時for(int k=0;k<table[m].size();k++){int v=table[m][k].v;int value=table[m][k].value;if(path[m]+value<path[v])//還能找到有比path[v]更小的距離return false;//說明有負環存在}}return true;//否則無負環}
}

設計思想

將求最短路徑看作是求以源點為根結點的一棵最短路徑樹，此時圖與起點均確定，因此最短路徑樹也就確定了，且最短路徑樹的層數一定不超過頂點個數V，即樹中兩頂點的比較更新次數不超過V-1輪。

實現

由于用鄰接矩陣遍歷邊時，復雜度會達到O(V的3次方)，因此我們使用鄰接表去實現

應用

由于求最短路徑條數時，BF算法會重復遍歷相同的頂點，因此在有多條最短路徑數時，最短路徑條數的累加會出錯。于是我們想到用set容器記錄前驅結點，通過遍歷去重后的前驅結點進行累加。
set容器的介紹

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int maxn=100;
const int INF=1000000000;
struct node{int v;//鄰接頂點int value;//對應邊權//通過構造函數實現定義同時初始化node(int a,int b):v(a),value(b){}
};
vector<node> table[maxn];
int n,edge,st,ed,weight[maxn];int path[maxn],num[maxn],w[maxn];
set<int> pre[maxn];//記錄前驅，以便去重void BF(int b){fill(path,path+maxn,INF);memset(num,0,sizeof(num));memset(w,0,sizeof(w));path[b]=0;w[b]=weight[b];num[b]=1;for(int i=0;i<n-1;i++){for(int j=0;j<n;j++){for(int k=0;k<table[j].size();k++){//記錄int v=table[j][k].v;int value=table[j][k].value;if(path[j]+value<path[v]){path[v]=path[j]+value;w[v]=w[j]+weight[v];num[v]=num[j];//小于覆蓋pre[v].clear();//清空pre[v].insert(j);//記錄最短路徑前驅}else if(path[j]+value==path[v]){if(w[v]<w[j]+weight[v])w[v]=w[j]+weight[v];pre[v].insert(j);//繼續記錄num[v]=0;//防止重復計數，清空//重新累加計數:通過遍歷前驅結點實現for( set<int>::iterator it=pre[v].begin();it!=pre[v].end();it++)num[v]+=num[*it];//*it=pre[j][k],即k的前驅}}}}}int main(){int v1,v2,weigh;cin>>n>>edge>>st>>ed;for(int i=0;i<n;i++)cin>>weight[i];for(int j=0;j<edge;j++){//構建鄰接表cin>>v1>>v2>>weigh;table[v2].push_back(node(v1,weigh));table[v1].push_back(node(v2,weigh));}BF(st);cout<<num[ed]<<" "<<w[ed]<<endl;return 0;
}