類似spfa?我也不太清楚

2019-11-11 00:24:19

字體：大中小

供稿：網(wǎng)友

在網(wǎng)上找了些spfa代碼，大多數(shù)給了我冗雜的感覺(jué)?？戳似渌枷牒笪艺罩鴮懥艘粋€(gè)，保存一下方便以后尋找不足并改進(jìn)。 spfa是bellman-ford的改進(jìn)，bellman-ford的想法是把每個(gè)邊都松弛一下，算法復(fù)雜度是V^2，大部分的時(shí)間浪費(fèi)在了查找新的點(diǎn)s和更新當(dāng)前點(diǎn)的最短距離d。我對(duì)于spfa的理解就是bfs或dfs的變形。先用鄰接表保存某個(gè)點(diǎn)的相鄰點(diǎn)（節(jié)點(diǎn)參數(shù) ：節(jié)點(diǎn)編號(hào)，兩點(diǎn)距離），這部分復(fù)雜度為o(E),然后用隊(duì)列保存被松弛的相鄰節(jié)點(diǎn)。如果某個(gè)點(diǎn)進(jìn)入隊(duì)列V次，說(shuō)明圖中存在負(fù)權(quán)回路代碼： bfs法這個(gè)是有向圖

#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判斷負(fù)權(quán)回路快

#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;}

如果有什么代碼什么問(wèn)題錯(cuò)誤希望大家能夠提出來(lái)，共同進(jìn)步

上一篇：TCP三次握手

下一篇：1078. Hashing (25)