代碼
import java.util.Scanner;
/**
* 解決帶負(fù)權(quán)邊的最短路徑算法——BellmanFord
* @author XZP
*
*/
public class BellmanFord {
public static void main(String[] args) {
int INF = 9999; // 定義一個(gè)認(rèn)為的最大值
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 頂點(diǎn)數(shù)
int M = sc.nextInt(); // 邊數(shù)
int[] dis = new int[N]; // 放最短路徑的距離
// 聲明uvw三個(gè)數(shù)組两踏，用于表示u[i]到v[i]兩個(gè)頂點(diǎn)之間的權(quán)重為w[i]
int[] u = new int[N];
int[] v = new int[N];
int[] w = new int[N];
// 讀入邊
for (int i = 0; i < M; i++) {
u[i] = sc.nextInt();
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
// 初始化dis數(shù)組:1號(hào)頂點(diǎn)到其他頂點(diǎn)之間的初始路程(下標(biāo)0開始)
for (int i = 1; i < N; i++) {
dis[i] = INF;
}
dis[0] = 0;
// BellmanFord算法的核心語(yǔ)句
for (int k = 0; k < N -1; k++) { // n個(gè)頂點(diǎn)的情況下昭齐，其中一個(gè)頂點(diǎn)到其他所有頂點(diǎn)之間至多有n-1條邊曙强，進(jìn)行n-1次松弛
for (int i = 0 ; i < M; i++) {
if (dis[v[i]] > dis[u[i]] + w[i]) {
dis[v[i]] = dis[u[i]] + w[i];
}
}
}
// 輸出結(jié)果
for (int i = 0; i < N; i++) {
System.out.print(dis[i] + " ");
}
}
}
幾點(diǎn)注意
- 時(shí)間復(fù)雜度O(M * N)
- 顯然還可以優(yōu)化
- 可用于檢測(cè)是否圖帶有負(fù)權(quán)邊
