快捷導(dǎo)航

Java Floyd算法求有權(quán)圖（非負權(quán)）的最短路徑并打印

更新時間：2019年07月15日 15:24:25 作者：花溪的小石頭

這篇文章主要介紹了Java Floyd算法求有權(quán)圖（非負權(quán)）的最短路徑并打印，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

狀態(tài)轉(zhuǎn)移方程：d(i,j) = min(d(i,j),d(i,k)+d(k,j))，其中i<k<j

思路對于每一個k(i<k<j)，全部遍歷下來之后，肯定會發(fā)生一次有效的比較

public class FloydTest {
 private static int[][] matrix;

 private static int[][] path;

 public static void main(String[] args) {

  initMatrixAndPath(
      new int[][]{
          {0, 1, 8, 5},
          {1, 0, 7, 6},
          {8, 7, 0, 2},
          {5, 6, 2, 0}}
  );


  floyd(matrix, path);
  printShortDistance();
  printShortDistanceDetail();
 }

 private static void initMatrixAndPath(int[][] matrix) {
  FloydTest.matrix = matrix;
  FloydTest.path = new int[matrix.length][matrix.length];

  for (int i = 0; i < FloydTest.matrix.length; i++) {
   for (int j = 0; j < FloydTest.matrix[i].length; j++) {
    path[i][j] = j;
   }
  }
 }

 private static void floyd(int[][] matrix, int[][] path) {
  for (int k = 0; k < matrix.length; k++) {
   for (int i = 0; i < matrix.length; i++)
    for (int j = 0; j < matrix.length; j++) {
     if (matrix[i][j] > matrix[i][k] + matrix[k][j]) {
      matrix[i][j] = matrix[i][k] + matrix[k][j];
      path[i][j] = path[i][k];
     }
    }
  }


 }

 private static String getNodeName(int nodeIndex) {
  return "v" + nodeIndex;
 }

 private static void printShortDistanceDetail() {
  for (int i = 0; i < matrix.length; i++) {
   for (int j = 0; j < matrix[i].length; j++) {
    int x = j;
    StringBuilder sb = new StringBuilder("最短路徑[v" + i + ",v" + j + "]為:");
    sb.append(getNodeName(x));
    sb.append("<--");
    while (path[i][j] != x) {
     x = path[i][x];
     sb.append(getNodeName(path[i][x]));
     sb.append("<--");
    }
    sb.append(getNodeName(i));

    System.out.println(sb);
   }

  }
 }

 private static void printShortDistance() {
  for (int i = 0; i < matrix.length; i++) {
   for (int j = 0; j < matrix[i].length; j++) {
    System.out.println("v" + i + "到" + "v" + j + "最短路徑為:" + matrix[i][j]);
   }
  }
 }
}

輸出結(jié)果

v0到v0最短路徑為:0
v0到v1最短路徑為:1
v0到v2最短路徑為:7
v0到v3最短路徑為:5
v1到v0最短路徑為:1
v1到v1最短路徑為:0
v1到v2最短路徑為:7
v1到v3最短路徑為:6
v2到v0最短路徑為:7
v2到v1最短路徑為:7
v2到v2最短路徑為:0
v2到v3最短路徑為:2
v3到v0最短路徑為:5
v3到v1最短路徑為:6
v3到v2最短路徑為:2
v3到v3最短路徑為:0
最短路徑[v0,v0]為:v0<--v0
最短路徑[v0,v1]為:v1<--v0
最短路徑[v0,v2]為:v2<--v3<--v0
最短路徑[v0,v3]為:v3<--v0
最短路徑[v1,v0]為:v0<--v1
最短路徑[v1,v1]為:v1<--v1
最短路徑[v1,v2]為:v2<--v1
最短路徑[v1,v3]為:v3<--v1
最短路徑[v2,v0]為:v0<--v3<--v2
最短路徑[v2,v1]為:v1<--v2
最短路徑[v2,v2]為:v2<--v2
最短路徑[v2,v3]為:v3<--v2
最短路徑[v3,v0]為:v0<--v3
最短路徑[v3,v1]為:v1<--v3
最短路徑[v3,v2]為:v2<--v3
最短路徑[v3,v3]為:v3<--v3