bellman-ford

0熱度

1回答

我正在使用JGraphT在Java中實現Bellman Ford最短路徑算法。由於存在一些邊緣，因此應優先選擇邊緣權重爲-1。例如：甲< - > B：10 甲< - > C：10 Ç< - > B：-1 乙< - > d ：10 所以在這種情況下，路徑應該看起來像A→C→B→D。子路徑A- > C-> B應優於A-> B。現在問題是：算法找到C和B之間的循環，以便C→B和B→C路徑被添加

0熱度

1回答

我執行bellman-ford有什麼問題？

我對這段代碼有什麼問題一無所知。它沒有按預期工作。其預期顯示從頂點1到N的最短路徑。但它在許多情況下失敗。一個這樣的情況下是它顯示了答案 1 25 -1 3 這是錯誤... 任何幫助，將不勝感激。謝謝。 #include <iostream> #include <cstdio> #include <vector> #include <list> using namespace st

0熱度

1回答

Bellman-Ford算法

我知道Bellman-Ford算法最多需要| V | - 如果圖形不包含負重量循環，則重複1次以找到最短路徑。有沒有辦法修改Bellman-Ford算法，以便在1次迭代中找到最短路徑？

-1熱度

1回答

查詢關於貝爾曼福特

我最近一直在研究貝爾曼福特算法。我懷疑如果從源頂點到達的有向圖中有負權重循環，那麼所有節點或某些節點都不存在最短的權重循環。這是bellman ford的實現。 //O(VE) #include <bits/stdc++.h> using namespace std; #define ll long long #define sl(n) scanf("%lld",&n) #define

0熱度

1回答

單源最短路徑實現：優先級與先進先出隊列

根據具體問題的不同，在單源最短路徑問題的背景下一般提到的兩種算法是Dijkstra算法和Bellman-Ford算法。 Dijkstra的算法以正邊權重工作，而Bellman-Ford算法是一種泛化，也允許負邊權重。如在Sedgewick的書「算法」（第4版）中實現的，Dijkstra的算法基於優先級隊列，而Bellman-Ford算法基於簡單的FIFO隊列。但是，對於我來說，看起來好像兩種隊列

0熱度

1回答

刪除邊緣後對最短路徑的影響

已經提供了有向圖的輸入，並且我找到了使用異步和同步Bellman-Ford算法的特定節點'T'的最短路徑。我試圖找出一些邊緣被刪除後最短路徑上的效果。在我的方法中，我試圖將刪除邊緣的起始節點處的距離標記爲無窮大，並嘗試應用異步Bellman-Ford，但是由於其他節點不會更新它們的值，因爲它們已經具有最短路徑最小值。任何人都可以幫助我找到一種方法來找到新的最短路徑，而不必在新圖上再次運行完整

1熱度

1回答

貝爾曼 - 福特算法步驟

假設有一個向圖，100-Vertexes如V_1---> V_2 ---> ... ---> V_100 邊緣的所有重量爲1。我們要使用Bellman-Ford算法來找到其他頂點1 (V_1)之間的最短路徑的數量和頂點。這個算法在每個步驟中以任意順序檢查所有邊。如果在一個步驟中V_1到所有其他頂點not changed之間的最短路徑（來自以前的值），算法將停止！ the number of ste

5熱度

2回答

貝爾曼福特隊列爲基礎的方法 - 算法，第4版

我正在研究爲Bellman-Ford algorithm單源最短路徑queue-based辦法從從書算法Robert Sedgewick and Kevin Wayne - Algorithms, 4th edition 源代碼出現在這個環節http://algs4.cs.princeton.edu/44sp/BellmanFordSP.java。我有兩點是一個疑問，另一個是代碼改進建議。在上

3熱度

1回答

Bellman-Ford改進：它工作嗎？

我試圖改進Bellman-Ford算法的性能，我想知道改進是否正確。我運行放鬆部分而不是V-1但是V次，並且我得到了一個布爾變量，如果在外部循環的迭代過程中發生任何放鬆，則設置爲true。如果沒有放鬆發生在n。迭代，其中n = < = V，它從具有最短路徑的循環中返回，但是如果它在n = V迭代處放鬆，那意味着我們有一個負循環。我認爲它可能會改善運行時間，因爲有時候我們不需要迭代V-1次來找到最

1熱度

1回答

bellman-ford可以在一次迭代中完成？

是否每個圖都有一個邊的順序，以便在根據此順序運行Bellman-Ford算法的單次迭代後，每個頂點都標記爲其到源的最短路徑？我很安靜相信答案是肯定的，但我想不出一個算法，該算法能夠找到邊緣的順序，感謝=]