Bellman-Flod算法

對于帶有負權值的圖，我們已經不能通過Dijkstra算法進行求解了
原因：Dijkstra每次都會找一個距源點（設為s）最近的點，然后將該距離定為這個點到源點的最短路徑；如果一個頂點u被加入了book[i])( book[i] == 1 說明這個s到u的路徑權值已被記錄，不可再更改)，但是如果存在v到u的權值為負，那么s經v到u到值要更小。
例如：

如果用Dijkstra跑只能得到2這個結果，但實際結果應該是1才對
s—->u 2
s—->v—-> 1

---

為解決帶負權值的問題，這里需要用到Bellman-Flod算法
問題描述：有如下帶負權值的圖，求從1號點到其他各點的最短路徑長度

Input：
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3

Output:
0 -3 -1 2 4

import java.util.Scanner; public class minPath {static int[] u = new int[10];static int[] v = new int[10];static int[] w = new int[10];static int[] dis = new int[10];static int n, m;static Scanner input = new Scanner(System.in);public static void main(String[] args) {n = input.nextInt();m = input.nextInt();for (int i = 1; i <= m; i++) {u[i] = input.nextInt();v[i] = input.nextInt();w[i] = input.nextInt();}for (int i = 1; i <= n; i++) {dis[i] = 99999999;}dis[1] = 0;bellmanFlod();for (int i = 1; i <= n; i++) {System.out.print(dis[i] + " ");}}private static void bellmanFlod() {/*** 由離散數學的理論得出，在一個n個頂點的圖中，任意兩點之間的最短路徑最多包含n-1條邊* */for (int i = 1; i <= n - 1; i++) {for (int j = 1; j <= m; j++) {if (dis[v[j]] > dis[u[j]] + w[j]) {dis[v[j]] = dis[u[j]] + w[j];}}}} }

時間復雜度：O(NM)

算法優化

優化版本一

優化原因：在實際操作中，很多時候不會進行n-1次，畢竟不是每個點都會達到n-1條邊的情況的，因此當不在能更新之后，我們就可以終止程序了，即使現在還沒進行到第n-1階段。

優化方法：添加一個一維數組備份來dis，如果新一輪的松弛中數組沒有發生變化，則可以提前跳出循環。

import java.util.Scanner;public class minPath {static int[] u = new int[10];static int[] v = new int[10];static int[] w = new int[10];static int[] dis = new int[10];static int[] bak = new int[10];static int n, m;static int check, flag;static Scanner input = new Scanner(System.in);public static void main(String[] args) {n = input.nextInt();m = input.nextInt();for (int i = 1; i <= m; i++) {u[i] = input.nextInt();v[i] = input.nextInt();w[i] = input.nextInt();}for (int i = 1; i <= n; i++) {dis[i] = 99999999;}dis[1] = 0;bellmanFlod();if (flag == 1) {System.out.println("此圖含有負權回路");} else {for (int j = 1; j <= n; j++) {System.out.print(dis[j] + " ");}}}private static void bellmanFlod() {/*** 由離散數學的理論得出，在一個n個頂點的圖中，任意兩點之間的最短路徑最多包含n-1條邊* */for (int i = 1; i <= n - 1; i++) {bak[i] = dis[i];for (int j = 1; j <= m; j++) {if (dis[v[j]] > dis[u[j]] + w[j]) {dis[v[j]] = dis[u[j]] + w[j];}}/*** 檢測dis是否還在變化* */check = 0;for (int j = 1; j <= n; j++) {if (bak[i] != dis[i]) {check = 1;break;}if (check == 0) {break;}}/*** 檢測負權回路* 原理：最短路徑所包含的邊做多為n-1條，在進行n-1次松弛之后如果還能繼續松弛成功，* 那說明此圖必定含有負權回路* */flag = 0;for (int j = 1; j <= m; j++) {if (dis[v[i]] > dis[u[i]] + w[i]) {flag = 1;}}}} }

優化原因：因為最短路徑做多有n-1條邊，所以Bellman-Ford算法做多有n-1個階段。而每個階段都要對每條邊進行“松弛操作”，使得“估計值”變為“確定值”。而對于本階段來說，上個階段松弛完的結果是不會再改變的，而原算法每個階段都會重新計算，浪費時間。

優化方法：每次僅對最短路“估計值”變化為“確定值”的頂點的所有出邊執行松弛操作，可以采用隊列進行優化
時間復雜度：O(NM)

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;public class minPath {static int[] u = new int[8];static int[] v = new int[8];static int[] w = new int[8];/*** first 要比 n 的值大1* next 要比 m 的值大1* */static int[] first = new int[6];static int[] next = new int[8];static int[] dis = new int[6];static int[] book = new int[6];static int n, m;static Queue<Integer> queue = new LinkedList<>();static Scanner input = new Scanner(System.in);public static void main(String[] args) {n = input.nextInt();m = input.nextInt();for (int i = 1; i <= n; i++) {dis[i] = 99999999;}dis[1] = 0;for (int i = 1; i <= n; i++) {first[i] = -1;}for (int i = 1; i <= m; i++) {u[i] = input.nextInt();v[i] = input.nextInt();w[i] = input.nextInt();/*** 建立鄰接表的關鍵語句！！！* */next[i] = first[u[i]];first[u[i]] = i;}queue.offer(1);book[1] = 1;bellomanFlodPlus();for (int i = 1; i <= n; i++) {System.out.print(dis[i] + " ");}}private static void bellomanFlodPlus() {while (!queue.isEmpty()) {/*** 當前的隊首元素* */int k = first[queue.peek()];while (k != -1) {if (dis[v[k]] > dis[u[k]] + w[k]) {dis[v[k]] = dis[u[k]] + w[k];/*** 用數組來判斷v[k]是否已經在隊列中* 不使用數組進行記錄的話，要迭代隊列，十分不方便* */if(book[v[k]] == 0) {queue.offer(v[k]);book[v[k]] = 1;}}k = next[k];}book[queue.peek()] = 0;queue.remove();}} }

總結

以上是生活随笔為你收集整理的图论算法（三）--最短路径 的Bellman-Flod [ 带负权值图 ] 的解法（JAVA ）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。