如果，上面的圖，如果用dij算法，那么dist[4] = 4, ?是得不到正確的結(jié)果的， 這個(gè)因?yàn)閐ist[3]先被確定是最小，然后用來(lái)更新dist[4]

但是存在負(fù)權(quán)，使得dist[3]更小，但是我們已經(jīng)把結(jié)點(diǎn)3標(biāo)記為不可用了（vis[3] = true)， 所以存在錯(cuò)誤

如何使得使得結(jié)點(diǎn)3可用呢？ 我們把判斷的條件給改一下，如果結(jié)點(diǎn)u出隊(duì)列之后，其權(quán)值為dist[u] 來(lái)得小， 那么就可以用它來(lái)更新其他的定點(diǎn)

這樣子，每個(gè)結(jié)點(diǎn)都可以多次入隊(duì)列， 使得dij可以處理負(fù)權(quán)

1 int dij(int x, int y, int n) 2 { 3 for (int i = 1; i <= n; ++i) 4 dist[i] = INF; 5 priority_queue<Edge> q; 6 Edge cur, tmp; 7 cur.dist = dist[x] = 0; 8 cur.v = x; 9 q.push(cur); 10 while (!q.empty()) 11 { 12 cur = q.top(); q.pop(); 13 int u = cur.v; 14 if (dist[u] < cur.dist)//如果cur.dist < dist[u]， 那么可以繼續(xù)更新其他頂點(diǎn)， 代替了條件vis[u] 15 continue; 16 for (int i = 0; i < g[u].size(); ++i) 17 { 18 int v = g[u][i].v; 19 if (dist[v] > dist[u] + g[u][i].dist) 20 { 21 tmp.dist = dist[v] = dist[u]+ g[u][i].dist; 22 tmp.v = v; 23 q.push(tmp); 24 } 25 } 26 } 27 return dist[y]; 28 }

?

?

bellaman__ford算法的無(wú)用操作

void relax(int u, int v,double weight) {if(dist[v] > dist[u] + weight)dist[v] = dist[u] + weight; } bool bellman_ford(int n, int m) {int i,j;for(i=0; i<n-1; ++i)//n-1循環(huán)for(j=0; j<m; ++j)//枚舉所有的邊去松弛最短路徑 {relax(g[j].u,g[j].v,g[j].weight);}bool flag = false;for(i=0; i<m; ++i)if(dist[g[i].v] > dist[g[i].u] + g[i].weight){flag = true;break;}return flag; }

如上述代碼所示， 我們枚舉每條邊， 看看能不能松弛最短路徑， 但這么做，其實(shí)做了很多的無(wú)用功， 比如說(shuō)如果 dist[g[j]] 沒(méi)有被松弛過(guò)或者松弛不成功，

那么relax(g[j].u,g[j].v,g[j].weight) 做的就是無(wú)用功

?

對(duì)于這個(gè)， 我們可以用隊(duì)列來(lái)優(yōu)化bellman算法， （上交的大神發(fā)明的，時(shí)間復(fù)雜度是O(ke)，k是常數(shù)，雖然后來(lái)被證實(shí)它證明的k是常數(shù)是錯(cuò)誤的）

如果結(jié)點(diǎn)u被更新過(guò)了， 那么才可以用它來(lái)更新它所指向的定點(diǎn)?

?

int spfa(int x, int y, int n) {for (int i = 1; i <= n; ++i)dist[i] = INF;queue<int> q;q.push(x);dist[x] = 0;while (!q.empty()){int u = q.front(); q.pop();vis[u] = false;for (int i = 0; i < g[u].size(); ++i){int v = g[u][i].v;if (dist[v] > dist[u] + g[u][i].dist){dist[v] = dist[u] + g[u][i].dist;//能更新就更新if (!vis[v])//如果結(jié)點(diǎn)在隊(duì)里里面，就不用重復(fù)入隊(duì)了 {q.push(v);vis[v] = true;}}}}return dist[y]; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/justPassBy/p/4646413.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的最短路最新心得的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。