您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“Java Bellman-Ford算法原理及實(shí)現(xiàn)方法”的有關(guān)知識(shí),在實(shí)際案例的操作過程中,不少人都會(huì)遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
如果遇到負(fù)權(quán)邊,則在沒有負(fù)環(huán)(回路的權(quán)值之和為負(fù))存在時(shí),可以采用 Bellman-Ford 算法求解最短路徑。該算法的優(yōu)點(diǎn)是變的權(quán)值可以是負(fù)數(shù)、實(shí)現(xiàn)簡單,缺點(diǎn)是時(shí)間復(fù)雜度過高。但是該算法可以進(jìn)行若干種優(yōu)化,以提高效率。
Bellman-Ford 算法與 Dijkstra 算法類似,都是以松弛操作作為基礎(chǔ)。Dijkstra 算法以貪心法選取未被處理的具有最小權(quán)值的節(jié)點(diǎn),然后對(duì)其進(jìn)行松弛操作;而 Bellman-Ford 算法對(duì)所有邊都進(jìn)行松弛操作,共 n-1 次。因?yàn)樨?fù)環(huán)可以無限制地減少最短路徑長度,所以吐過發(fā)現(xiàn)第 n 次操作仍然可松弛,則一定存在負(fù)環(huán)。Bellman-Ford 算法最長運(yùn)行時(shí)間為O(nm),其中 n 和 m 分別是節(jié)點(diǎn)數(shù)和邊數(shù)。
1 數(shù)據(jù)結(jié)構(gòu)
因?yàn)樾枰眠呥M(jìn)行松弛,因此采用邊集數(shù)組存儲(chǔ)。每條邊都有三個(gè)域:兩個(gè)端點(diǎn)a和b,以及邊權(quán)w
2 松弛操作
對(duì)所有的邊 j(a,b,w),如果 dis[e[j]b]>dis[e[j].a]+e[j].w,則松弛,另 dis[e[j]b]=dis[e[j].a]+e[j].w。其中,dis[v] 表示從源點(diǎn)到節(jié)點(diǎn) v 的最短路徑長度。
3 重復(fù)松弛操作 n-1 次
4 負(fù)環(huán)判斷
再執(zhí)行一次松弛操作,如果仍然可以松弛,則說明右負(fù)環(huán)。
package graph.bellmanford; import java.util.Scanner; public class BellmanFord { static node e[] = new node[210]; static int dis[] = new int[110]; static int n; static int m; static int cnt = 0; static { for (int i = 0; i < e.length; i++) { e[i] = new node(); } } static void add(int a, int b, int w) { e[cnt].a = a; e[cnt].b = b; e[cnt++].w = w; } static boolean bellman_ford(int u) { // 求源點(diǎn) u 到其它頂點(diǎn)的最短路徑長度,判負(fù)環(huán) for (int i = 0; i < dis.length; i++) { dis[i] = 0x3f; } dis[u] = 0; for (int i = 1; i < n; i++) { // 執(zhí)行 n-1 次 boolean flag = false; for (int j = 0; j < m; j++) // 邊數(shù) m 或 cnt if (dis[e[j].b] > dis[e[j].a] + e[j].w) { dis[e[j].b] = dis[e[j].a] + e[j].w; flag = true; } if (!flag) return false; } for (int j = 0; j < m; j++) // 再執(zhí)行 1 次,還能松弛說明有環(huán) if (dis[e[j].b] > dis[e[j].a] + e[j].w) return true; return false; } static void print() { // 輸出源點(diǎn)到其它節(jié)點(diǎn)的最短距離 System.out.println("最短距離:"); for (int i = 1; i <= n; i++) System.out.print(dis[i] + " "); System.out.println(); } public static void main(String[] args) { int a, b, w; Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); for (int i = 0; i < m; i++) { a = scanner.nextInt(); b = scanner.nextInt(); w = scanner.nextInt(); add(a, b, w); } if (bellman_ford(1)) // 判斷負(fù)環(huán) System.out.println("有負(fù)環(huán)!"); else print(); } } class node { int a; int b; int w; }
1 沒有負(fù)環(huán)的測試
2 有負(fù)環(huán)的測試
“Java Bellman-Ford算法原理及實(shí)現(xiàn)方法”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。