在網上找了些spfa代碼，大多數給了我冗雜的感覺。看了其思想后我照著寫了一個，保存一下方便以后尋找不足并改進。 spfa是bellman-ford的改進，bellman-ford的想法是把每個邊都松弛一下，算法復雜度是V^2，大部分的時間浪費在了查找新的點s和更新當前點的最短距離d。我對于spfa的理解就是bfs或dfs的變形。先用鄰接表保存某個點的相鄰點（節點參數 ： 節點編號，兩點距離），這部分復雜度為o(E),然后用隊列保存被松弛的相鄰節點。 如果某個點進入隊列V次，說明圖中存在負權回路 代碼： bfs法 這個是有向圖
#define N 500#define INF 0x3f3f3f3f#define mem(arr,num) memset(arr,num,sizeof(arr))/***************************************/int V, E;struct edge{ int v, w;};int d[N];int num[N];bool used[N];vector <edge> e[N];bool spfa(int s){ fill(d, d + V + 1, INF); mem(used, 0); d[s] = 0; num[s] = 1; queue <int> que; que.push(s); while (!que.empty()){ int x = que.front(); que.pop(); for (int i = 0; i < e[x].size(); i++){ int next = e[x][i].v; if (d[next]>d[x] + e[x][i].w) { d[next] = e[x][i].w + d[x]; if (!used[next]) { num[next]++; used[next] = true; que.push(next); } if (num[next] == V) return false; } } used[x] = false; } return true;}int main(){ cin >> V >> E; for (int i = 1; i <= E; i++){ int u; edge ed; cin >> u; cin >> ed.v >> ed.w; e[u].push_back(ed); } if (spfa(1)){ cout << d[3] << endl; } else cout << "NO" << endl;}然后是dfs類似的 dfs判斷負權回路快
#define N 500#define INF 0x3f3f3f3f/***************************************/int V, E;struct edge{ int v, w;};int d[N];int num[N];vector <edge> e[N];bool spfa(int s){ for (int i = 0; i < e[s].size(); i++){ int v = e[s][i].v; if (d[v]>d[s] + e[s][i].w){ d[v] = d[s] + e[s][i].w; num[v]++; if (num[v] == V) return true; } if (spfa(v)){ return true; } } return false;}int main(){ cin >> V >> E; for (int i = 1; i <= E; i++){ int u; edge ed; cin >> u ; cin >> ed.v >> ed.w; e[u].push_back(ed); } fill(d, d + V + 1, INF); d[1] = 0; num[1] = 1; if (!spfa(1)){ cout << d[3] << endl; } else cout << "NO" << endl;}如果有什么代碼什么問題錯誤希望大家能夠提出來，共同進步
新聞熱點
疑難解答
