背景
NBA超级后场组合灯泡组合(Harden和CP3)休赛期来到中国玩耍,他们两人打算在四个城市进行玩耍,最后他们选择了北京、上海、西安和长沙。假设这四个城市之间有些城市之前有航线,而有些城市之间没有航线。为了方便行程,出发前,他们想要知道任意两个城市之间的最短路程。如果下图就是航线图:
数据结构
我们使用一个二维数组Path来存储上述图的信息。比如说1号城市到二号城市之间的距离可以存储为Path[0][1] = 2,而2号城市无法直接到达1号城市我们记Path[1][0] = Infinity。另外我们约定一个城市到达本身的距离为0,即Path[0][0] = 0。
思路
想要使两个城市(x,y)之间的距离变短,此时我们可以引入第三个城市作为中转点(z),本来是x->y,现在变成x->z->y,只有这样才有可能缩短x和y之间的距离,那么这个中转点z到底是哪个城市,或者可以说这个z代表的是多个中转点,因为有时候经过多个中转点,x和*y之间的距离会更短。下面我们通过一步步的添加中转点,来更新两点之间的最短距离。
过程
我们依照最上面的航线图,解释如何得到最短路径。
当任意两个城市之间不允许经过第三个城市的时候,得到的矩阵如下:
第一步:
现在我们只允许经过1号城市这个中转点,这个时候如何求解任意两点之间的最短距离。我们只需进行如下比较:
Path[i][0] + Path[0][j] < Path[i][j]
其中Path[i][j]表示的是城市i+1和j+1(因为JS中,数组索引从0开始)之间的距离。而Path[i][0] + Path[0][j] 表示的是先从i+1到1号城市,再从1到j+1的距离之和。
这个时候把i从0~n-1循环,把j从0~n-1循环,既可以得到当经过中转点1号城市的时候,任意两点之间的最短距离。
代码实现:
for(var i = 0; i < n; i++ ){
for(var j = 0; j < n; j++){
if(Path[i][0] + Path[0][j] < Path[i][j]){
Path[i][j] = Path[i][0] + Path[0][j];
}
}
}
这个时候我们可以把最短距离矩阵更新为:
从上图可以看出,在经过中转点:1号城市的时候,有几个城市之间的最短距离减少了。
接下来,我们要做的就是增加中转点:2号城市。要执行的代码如下:
for(var i = 0; i < n; i++ ){
for(var j = 0; j < n; j++){
if(Path[i][0] + Path[0][j] < Path[i][j]){
Path[i][j] = Path[i][0] + Path[0][j];
}
}
}
for(var i = 0; i < n; i++ ){
for(var j = 0; j < n; j++){
if(Path[i][1] + Path[1][j] < Path[i][j]){
Path[i][j] = Path[i][1] + Path[1][j];
}
}
}
我们可以继续更新距离矩阵为:
从上图可以看出,增加中转点后,有些城市之间的最短距离进一步减小。
同理,我们进一步增加中转点城市3和城市4,就可以得到最终的距离矩阵为:
下面给出一个完整函数:
//接收一个参数,参数即用二维数组存储的距离矩阵
function floyd(Path){
var n = Path && Path.length;
var m = n && Path[0].length;
if(m && n && m===n){
for(var k = 0; k < n; k++){
for(var i = 0; i < n; i++ ){
for(var j = 0; j < n; j++){
if(Path[i][k] + Path[k][j] < Path[i][j]){
Path[i][j] = Path[i][k] + Path[k][j];
}
}
}
}
}
}
注意:Floyd算法不能解决带有“负权回路”(或者叫“负权环”)的图。因为带有“负权回路”的图没有最短路。