第二天
小灰的思路如下：
第一步秉犹，利用迪杰斯特拉算法的距離表，求出從頂點A出發(fā)稚晚，到其他各個頂點的最短距離：
第二步崇堵，繼續(xù)使用迪杰斯特拉算法，求出從頂點B出發(fā)客燕，到其他各個頂點的最短距離鸳劳。
小編是一個有著6年工作經驗的工程師，關于C++也搓，編程赏廓，自己有做材料的整合，一個完整的C++編程學習路線傍妒，學習資料和工具幔摸，能夠進我的群7253，-91790收取颤练，免費送給大家既忆，希望你也能憑著自己的努力，成為下一個優(yōu)秀的程序員
第三步嗦玖，從頂點C出發(fā)患雇，到各個頂點的最短距離。
第四步宇挫，從頂點D出發(fā)......
.......
就像這樣庆亡，一直遍歷到頂點G。
這個思路的時間復雜度是多少呢捞稿？
假如圖中有n個頂點又谋，如果不考慮堆優(yōu)化拼缝，一次迪杰斯特拉算法的時間復雜度是O（n^2）。所以彰亥，把每一個頂點都計算一遍咧七，總的時間復雜度是O（n^3）。
————————————
舉一個栗子：
上圖的頂點A和頂點C沒有直接相連的邊任斋，它們之間的直接距離是無窮大继阻。
如果以B作為“中繼頂點”，此時A到C的最短路徑就是A-B-C废酷，最短距離是3+2=5瘟檩。
再舉一個栗子：
上圖的頂點A和頂點C直接相連，距離是6澈蟆。但是存在一條“迂回”路徑A-B-C墨辛，距離是3+2=5<6。
所以趴俘，經過中繼頂點B睹簇，從A到C的最短距離可以是5。
下面我們來看一看Floyd算法的詳細步驟寥闪。
1.要實現(xiàn)Floyd算法太惠，首先需要構建帶權圖的鄰接矩陣：
在鄰接矩陣當中，每一個數(shù)字代表著從某個頂點到另一個頂點的直接距離疲憋，這個距離是沒有涉及到任何中繼頂點的凿渊。
2.此時假定只允許以頂點A作為中繼頂點，那么各頂點之間的距離會變成什么樣子呢缚柳？
B和C之間的距離原本是無窮大埃脏，此時以A為中繼喂击，距離縮短為AB距離+AC距離=
5+2=7。
更新對應矩陣元素（橙色區(qū)域代表頂點A到其他頂點的臨時距離）：
3.接下來以頂點A翰绊、B作為中繼頂點，那么各頂點之間的距離會變成什么樣子呢监嗜？
A和D之間的距離原本是無窮大谐檀，此時以B為中繼裁奇，距離縮短為AB距離+BD距離=5+1=6。
A和E之間的距離原本是無窮大刽肠，此時以B為中繼溃肪，距離縮短為AB距離+BE距離=5+6=11免胃。
更新對應矩陣元素（橙色區(qū)域代表頂點B到其他頂點的臨時距離）：
4.接下來以頂點A羔沙、B厨钻、C作為中繼頂點，那么各頂點之間的距離會變成什么樣子呢诗充？
A和F之間的距離原本是無窮大诱建，此時以C為中繼，距離縮短為AC距離+CF距離=2+8=10励翼。
更新對應矩陣元素（橙色區(qū)域代表頂點C到其他頂點的臨時距離）：
.........
.........
以此類推，我們不斷引入新的中繼頂點抓狭，不斷刷新矩陣中的臨時距離否过。
最終，當所有頂點都可以作為中繼頂點時药磺，我們的距離矩陣更新如下：
此時煤伟，矩陣中每一個元素癌佩，都對應著某頂點到另一個頂點的最短距離围辙。
為什么這么說呢姚建？讓我們回顧一下動態(tài)規(guī)劃的兩大要素：
問題的初始狀態(tài)
問題的狀態(tài)轉移方程式
對于尋找圖的所有頂點之間距離的問題吱殉，初始狀態(tài)就是頂點之間的直接距離厘托，也就是鄰接矩陣催烘。
而問題的狀態(tài)轉移方程式又是什么呢缎罢？
假設新引入的中繼頂點是n，那么：
頂點i 到 頂點j 的新距離 = Min（頂點i 到 頂點j 的舊距離舰始，頂點i 到 頂點n 的距離+頂點n 到 頂點j 的距離）
final
static
int
INF
=
Integer
.
MAX_VALUE
;
public
static
void
floyd
(
int
[][]
matrix
){
//循環(huán)更新矩陣的值
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
][
k
]
==
INF
||
matrix
[
k
][
j
]
==
INF
)
{
continue
;
}
matrix
[
i
][
j
]
=
Math
.
min
(
matrix
[
i
][
j
],
matrix
[
i
][
k
]
+
matrix
[
k
][
j
]);
}
}
}
// 打印floyd最短路徑的結果
System
.
out
.
printf
(
"最短路徑矩陣:
"
);
for
(
int
i
=
0
;
i
<
matrix
.
length
;
i
++)
{
for
(
int
j
=
0
;
j
<
matrix
.
length
;
j
++)
System
.
out
.
printf
(
"%3d "
,
matrix
[
i
][
j
]);
System
.
out
.
printf
(
"
"
);
}
}
public
static
void
main
(
String
[]
args
)
{
int
[][]
matrix
=
{
{
0
,
5
,
2
,
INF
,
INF
,
INF
,
INF
},
{
5
,
0
,
INF
,
1
,
6
,
INF
,
INF
},
{
2
,
INF
,
0
,
6
,
INF
,
8
,
INF
},
{
INF
,
1
,
6
,
0
,
1
,
2
,
INF
},
{
INF
,
6
,
INF
,
1
,
0
,
INF
,
7
},
{
INF
,
INF
,
8
,
2
,
INF
,
0
,
3
},
{
INF
,
INF
,
INF
,
INF
,
7
,
3
,
0
}
};
floyd
(
matrix
);
}
