總目錄：地址如下看總綱
1持偏、應(yīng)用場景-最短路徑問題
建國時期逛钻，史萊村鄉(xiāng)有7個村莊(A, B, C, D, E, F, G) 肺樟，現(xiàn)在有六個郵差忧吟，從G點出發(fā)依疼，需要分別把郵件分別送到 A, B, C , D, E, F 六個村莊高蜂，各個村莊的距離用邊線表示(權(quán)) 椎眯，比如 A – B 距離 5公里
問：
1、如何計算出G村莊到 其它各個村莊的最短距離?
2再姑、如果從其它點出發(fā)到各個點的最短距離又是多少?
2萌抵、弗洛伊德(Floyd)算法介紹
（1）和Dijkstra算法一樣，弗洛伊德(Floyd)算法也是一種用于尋找給定的加權(quán)圖中頂點間最短路徑的算法。
（2）該算法名稱以創(chuàng)始人之一绍填、1978年圖靈獎獲得者萎坷、斯坦福大學(xué)計算機科學(xué)系教授羅伯特·弗洛伊德命名
弗洛伊德算法(Floyd)計算圖中各個頂點之間的最短路徑
（3）迪杰斯特拉算法用于計算圖中某一個頂點到其他頂點的最短路徑。
（4）弗洛伊德算法 VS 迪杰斯特拉算法：迪杰斯特拉算法通過選定的被訪問頂點沐兰，求出從出發(fā)訪問頂點到其他頂點的最短路徑哆档；弗洛伊德算法中每一個頂點都是出發(fā)訪問點，所以需要將每一個頂點看做被訪問頂點住闯，求出從每一個頂點到其他頂點的最短路徑瓜浸。
3、弗洛伊德算法思路
1比原、說明：不必插佛，深究
（1）設(shè)置頂點vi到頂點vk的最短路徑已知為Lik，頂點vk到vj的最短路徑已知為Lkj量窘，頂點vi到vj的路徑為Lij雇寇，則vi到vj的最短路徑為：min((Lik+Lkj),Lij)，vk的取值為圖中所有頂點蚌铜，則可獲得vi到vj的最短路徑
（2）至于vi到vk的最短路徑Lik或者vk到vj的最短路徑Lkj锨侯，是以同樣的方式獲得
2、圖解：主要學(xué)習(xí)方式
核心是兩個二維數(shù)據(jù)：一是初始的各頂點的距離表冬殃，二是初始前驅(qū)頂點關(guān)系表囚痴，還有三層循環(huán)
步驟圖：
（1）廣度大圖
（2）
（3）根據(jù)三種情況，演變出箭頭指向圖审葬，為三種情況的變化
（4）
（5）說明：
情況一:將C-G從N替換為9深滚，因為這樣更短
情況二:將C-B從N替換為12,因為距離更短
情況三:將G-B不替換，因為原本不經(jīng)過A的時候距離才3涣觉，經(jīng)過之后距離為7痴荐，更遠了，所以不替換
4官册、代碼
public class FloydAlgorithm {
public static void main(String[] args) {
// 測試圖是否創(chuàng)建成功
char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
// 創(chuàng)建鄰接矩陣
int[][] matrix = new int[vertex.length][vertex.length];
final int N = 65535;
matrix[0] = new int[]{0, 5, 7, N, N, N, 2};
matrix[1] = new int[]{5, 0, N, 9, N, N, 3};
matrix[2] = new int[]{7, N, 0, N, 8, N, N};
matrix[3] = new int[]{N, 9, N, 0, N, 4, N};
matrix[4] = new int[]{N, N, 8, N, 0, 5, 4};
matrix[5] = new int[]{N, N, N, 4, 5, 0, 6};
matrix[6] = new int[]{2, 3, N, N, 4, 6, 0};
// 創(chuàng)建 Graph 對象
Graph graph = new Graph (vertex.length, matrix, vertex);
// 調(diào)用弗洛伊德算法
graph.floyd ();
graph.show ();
}
}
// 構(gòu)建圖
class Graph {
private char[] vertex; // 存放頂點的數(shù)組
private int[][] dis; // 保存各個頂點出發(fā)到其他頂點的距離（同樣也是保留最終結(jié)果）
private int[][] pre; // 保存到達目標頂點的前驅(qū)頂點
/**
* 構(gòu)造器
*
* @param length 定義大小
* @param matrix 鄰接矩陣
* @param vertex 頂點數(shù)組
*/
public Graph(int length, int[][] matrix, char[] vertex) {
this.vertex = vertex;
this.dis = matrix;
this.pre = new int[length][length];
// 初始化 pre 數(shù)據(jù)生兆，注：存放應(yīng)是前驅(qū)頂點的下標
for (int i = 0; i < length; i++) {
Arrays.fill (pre[i], i);
}
}
// 顯示 pre 和 dis 兩個二位數(shù)組
public void show() {
// 為了便于閱讀，進而優(yōu)化輸出
char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
for (int k = 0; k < dis.length; k++) {
// 先輸出前驅(qū)數(shù)組 pre 的一行
for (int i = 0; i < dis.length; i++) {
System.out.print (pre[k][i] + " ");
}
// 再輸出dis 數(shù)組的一行
for (int i = 0; i < dis.length; i++) {
System.out.print ("(" + vertex[k] + "到" + vertex[i] + "的最短路徑是" + dis[k][i] + ") ");
}
System.out.println ( );
System.out.println ( );
}
}
// 核心：弗洛伊德算法, 比較容易理解攀隔，而且容易實現(xiàn)（三層循環(huán)）
public void floyd() {
// 變量保持距離
int len = 0;
// 對中間頂點遍歷皂贩， k 就是中間頂點的下標 [A, B, C, D, E, F, G]
for (int k = 0; k < dis.length; k++) {
// 從i頂點開始出發(fā) [A, B, C, D, E, F, G]
for (int i = 0; i < dis.length; i++) {
// 到達j頂點 // [A, B, C, D, E, F, G]
for (int j = 0; j < dis.length; j++) {
// 求出從i 頂點出發(fā)栖榨，經(jīng)過 k中間頂點昆汹，到達 j 頂點距離
len = dis[i][k] + dis[k][j];
if (len < dis[i][j]) { // 若len小于 dis[i][j]
dis[i][j] = len; // 更新距離
pre[i][j] = pre[k][j]; // 更新前驅(qū)頂點
}
}
}
}
}
}
5、倉庫坐標
