Floyd-Warshall算法败匹，簡(jiǎn)稱Floyd算法巢株，用于求解任意兩點(diǎn)間的最短距離。如下圖恢口，表示一個(gè)用鄰接矩陣表示的圖聂渊，如何求任意兩點(diǎn)之間的距離呢差购？
當(dāng)任意兩點(diǎn)之間不允許經(jīng)過第三個(gè)點(diǎn)時(shí)，這些點(diǎn)之間的最短距離就是初始距離汉嗽。
第一步：只允許經(jīng)過0號(hào)頂點(diǎn)欲逃，求任意兩點(diǎn)之間的最短路程。這時(shí)候只需要判斷map[i][0] + map[0][j] 是否比map[i][j]要小即可饼暑。map[i][j]表示從i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)之間的路程稳析，map[i][0] + map[0][j]表示的是從i號(hào)頂點(diǎn)先到0號(hào)頂點(diǎn)，再從0號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的路程之和弓叛。代碼如下：
<pre>
//經(jīng)過0號(hào)頂點(diǎn)
for i in 0..<map.count {
for j in 0..<map.count {
if map[i][j] > (map[i][0] + map[0][j]) {
map[i][j] = (map[i][0] + map[0][j])
}
}
}
</pre>第二部：在第一步的基礎(chǔ)上彰居，只允許經(jīng)過1號(hào)頂點(diǎn)
<pre>
//經(jīng)過1號(hào)頂點(diǎn)
for i in 0..<map.count {
for j in 0..<map.count {
if map[i][j] > (map[i][1] + map[1][j]) {
map[i][j] = (map[i][1] + map[1][j])
}
}
}
</pre>以此類推，最后允許通過所有的頂點(diǎn)作為中轉(zhuǎn)撰筷，就能得出任意兩點(diǎn)之間的最短路程陈惰。Floyd-Warshall算法的核心代碼只有以下五行！
<pre>
for k in 0..<map.count {
for i in 0..<map.count {
for j in 0..<map.count {
if map[i][j] > (map[i][k] + map[k][j]) {
map[i][j] = (map[i][k] + map[k][j])
}
}
}
}
</pre>完整代碼如下：
<pre>
let max:Int = 10000 //用來表示最大值∞毕籽，表示兩個(gè)頂點(diǎn)之間無邊
var map = [[0, 2, 6, 4],
[max, 0, 3, max],
[7, max, 0, 1],
[5, max, 12, 0]]
func floyd(map: inout [Array<Int>]) {
for k in 0..<map.count {
for i in 0..<map.count {
for j in 0..<map.count {
if map[i][j] > (map[i][k] + map[k][j]) {
map[i][j] = (map[i][k] + map[k][j])
}
}
}
}
}
floyd(map: &map)
print(map) //[[0, 2, 5, 4], [9, 0, 3, 4], [6, 8, 0, 1], [5, 7, 10, 0]]
</pre>
