1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class Floyed {
  private int[][] matrix;
  private int[][] preVertex;
  private int vertexLen = 3;
  public Floyed() {
    matrix = new int[vertexLen][vertexLen];
    matrix[0] = new int[]{0, 1, 10};
    matrix[1] = new int[]{1, 0, 2};
    matrix[2] = new int[]{10, 2, 0};

    // preVertex尋找前一個頂點，i是出發頂點，j是終點
    preVertex = new int[vertexLen][vertexLen];
    for (int i = 0; i < preVertex.length; i++) {
      // 預設前一個頂點是i出發頂點，若沒有中間頂點
      // i → j，是直達，j頂點的前一個頂點是i
      Arrays.fill(preVertex[i], i);
    }
  }

  public void floyed() {
    int len = 0;
    for (int k = 0; k < vertexLen; k++) {
      for (int i = 0; i < vertexLen; i++) {
        for (int j = 0; j < vertexLen; j++) {
          len = matrix[i][k] + matrix[k][j];
          if (len < matrix[i][j]) {
            matrix[i][j] = len;
            preVertex[i][j] = preVertex[k][j];
          }
        }
      }
    }
  }

  public void print() {
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix.length; j++) {
        System.out.print(matrix[i][j] + ", ");
      }
      System.out.println();
    }
    System.out.println();
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix.length; j++) {
        System.out.print(preVertex[i][j] + ", ");
      }
      System.out.println();
    }
  }

  // 參數出發頂點i,終點j
  // 印出的結果是呈現倒敘的方式，根據箭頭的方法來看路徑
  public void printPath(int i, int j) {
    // 終點
    System.out.print(j);
    // 出發頂點i → 終點j，前一個頂點是誰？
    int pre = preVertex[i][j];
    // 若前一個頂點是出發頂點i，就代表沒有中間頂點k。
    // 若前一個頂點「不是」出發頂點i，就代表有中間頂點，繼續找，直到前一個頂點為i(出發頂點)。
    while (pre != i) {
      System.out.print("<-" + pre);
      // 繼續找前一個頂點，i是出發頂點是固定
      // 直到前一個頂點是i，pre == i，就離開迴圈
      pre = preVertex[i][pre];
    }
    // 出發頂點
    System.out.print("<-" + i);
  }

  public static void main(String[] args) {
    Floyed floy = new Floyed();
    floy.floyed();
    floy.print();
    // 找頂點2 → 頂點0之間的路徑
    floy.printPath(2,0);
  }
}

1
2
3
4
5
6
7
8
9
  public void printPath(int i, int j) {
    if (preVertex[i][j] == -1) {
      System.out.println(i + "->" + j);
      return;
    }
    int k = preVertex[i][j];
    printPath(i,k);
    printPath(k,j);
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class Floyed {
  private int[][] matrix;
  private int[][] preVertex;
  private int vertexLen = 3;
  public Floyed() {
    matrix = new int[vertexLen][vertexLen];
    matrix[0] = new int[]{0, 1, 10};
    matrix[1] = new int[]{1, 0, 2};
    matrix[2] = new int[]{10, 2, 0};

    preVertex = new int[vertexLen][vertexLen];
    for (int i = 0; i < preVertex.length; i++) {
      Arrays.fill(preVertex[i], -1);
    }
  }

  public void floyed() {
    int len = 0;
    for (int k = 0; k < vertexLen; k++) {
      for (int i = 0; i < vertexLen; i++) {
        for (int j = 0; j < vertexLen; j++) {
          len = matrix[i][k] + matrix[k][j];
          if (len < matrix[i][j]) {
            matrix[i][j] = len;
            preVertex[i][j] = k;
          }
        }
      }
    }
  }

  public void print() {
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix.length; j++) {
        System.out.print(matrix[i][j] + ", ");
      }
      System.out.println();
    }
    System.out.println();
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix.length; j++) {
        System.out.print(preVertex[i][j] + ", ");
      }
      System.out.println();
    }
  }

  public void printPath(int i, int j) {
    if (preVertex[i][j] == -1) {
      System.out.println(i + "->" + j);
      return;
    }
    int k = preVertex[i][j];
    printPath(i,k);
    printPath(k,j);
  }

  public static void main(String[] args) {
    Floyed floy = new Floyed();
    floy.floyed();
    floy.print();
    floy.printPath(0,2);
  }
}