Swift最短路径之Floyd-Warshall算法

Floyd-Warshall算法，简称Floyd算法，用于求解任意两点间的最短距离。如下图，表示一个用邻接矩阵表示的图，如何求任意两点之间的距离呢？

floyd.png

• 当任意两点之间不允许经过第三个点时，这些点之间的最短距离就是初始距离。

• 第一步：只允许经过0号顶点，求任意两点之间的最短路程。这时候只需要判断map[i][0] + map[0][j] 是否比map[i][j]要小即可。map[i][j]表示从i号顶点到j号顶点之间的路程，map[i][0] + map[0][j]表示的是从i号顶点先到0号顶点，再从0号顶点到j号顶点的路程之和。代码如下：
  <pre>
  //经过0号顶点
  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>

• 第二部：在第一步的基础上，只允许经过1号顶点
  <pre>
  //经过1号顶点
  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>

• 以此类推，最后允许通过所有的顶点作为中转，就能得出任意两点之间的最短路程。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 //用来表示最大值∞，表示两个顶点之间无边
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>