【第二十四天 - Floyd-Warshall介绍】

Q1. Floyd-Warshall 是什麽

一种利用 Dynamic Programming ，求 Graph 中两点之间最短路径的演算法。

考虑 A, B 两点之间的最短路径，若有经过 k 点，则：

A, B 两点之间的最短路径 = A, k 两点之间的最短路径 + k, B 两点之间的最短路径

我们可以将含有 n 个节点的最短路径问题分解成 n 个「是否经过第 k 点」的问题。

以下图为例，计算 节点 0 与 节点 3 之间的最短路径长。由於 节点 0 和 节点 3 作为起点与终点，必然会在路径中被经过，因此我们将「路径只经过 节点 0 和 节点 3 」作为初始状态，再陆续考虑最短路径是否会经过其他节点。

1. 初始状态，最短路径长为 15：
   

2. 考虑 节点 1 是否为中继站之一：

   • 如果是，则路径长应为 节点 0 到节点 1 的最短路径长 + 节点 1 到 节点 3 的最短路径长
   • 如果否，则路径长应不受节点 1 影响，而是原先尚未考虑节点 1 时的路径长。

• 在此例中，经过 k 可以得到较短的路径长 9
  

3. 继续考虑下一个节点，直到所有节点都计算过：
   以此例而言，若经过 节点 2 ，其路径长为 12，没有比原先的路径长短，因此最终得到答案为 9 。
   

• 从上述例子中，可以归纳出下列关系：

• 假设已经考虑了 k - 1 个节点，现在要考虑第 k 个节点是否为最短路径中的中继站，会有两种可能的最短路径：

  • 最短路径有经过 k 点：其路径长为 A, k 两点之间的最短路径长 + k, B 两点之间的最短路径长
  • 最短路径没有经过 k 点：则表示最短路径没有经过 k 点，因此最短路径与未考虑 k 点时相同。

• 在两种可能路径中，较短者方为真正的最短路径。

• 综上所述，可列出以下递回关系式：

考虑 k 个中继节点时， AB 之间的最短路径长 = min(
	Ak 两点之间的最短路径长 + kB 两点之间的最短路径长,
	考虑 k - 1 个中继节点时， AB 之间的最短路径长
)

# 令 d(A, B, k) 表示 「考虑 k 个中继节点时， AB 之间的最短路径长」
=> d(A, B, k) = min( 
                    d(A, k, k - 1) + d(k, B, k - 1),
                    d(A, B, k - 1)
                    )

• 可以发现，当我们在计算 AB 之间的最短路径 时，会需要考虑 Ak 两点之间的最短路径长 和 kB 两点之间的最短路径长，纵然在上述例子中可以很容易的算出来，但回顾递回关系式，其中的 d(A, k, k - 1) + d(k, B, k - 1) 要每次都计算的话，不仅不好实作，也耗费效能，因此此时正是使用 Dynamic Programming 的时机 (DP：将已经计算好的结果记录下来，下一次使用就可以拿)。

• Floyd-Warshall 的实作逻辑

1. 先计算每个点直达另一个点的成本/权重/距离。 (若无法直达，则以无限大代表)
2. 总共有 0~N 个点，我们依序计算 min(原本的成本, 经过第k个点的成本)

• 以下图为例
  

  • 我们先计算每个点直达其他点的成本
    

• 接着我们依序计算计算经过 第0点的成本、第1点的成本...第3点的成本

  • 首先是经过第 0 点
    

  • 接着是经过第 1 点
    

  • 接着是经过第2点
    

  • 最後是经过第3点
    

• 计算完，这个表格就会是某个点抵达另外一个点最短距离，回到题目，我们要求 0→3 最短距离，可以从表格中得知最短距离为 9
  
  

• 在以下情况不适合使用 Floyd-Warshall 计算最短路径

  • 当绕一个 cycle 後为负，也就是负周期的情况 (可能导致负无穷大)
  • 节点数量过多 (导致时间复杂度过高)

Q2. 学会 Floyd-Warshall 概念可以做什麽 ?

• 求 Graph 中两点之间的最短路径 (在无负周期情况下)

Lab. 明天要解的题目：1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

• 题目连结：https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

• 题目叙述

  • 有 n 个城市，编号从 0 ~ n-1，题目会给一些边，从 i 点到 j 点的权重
  • distanceThreshold 类似游戏中的精力值，最多只能走 distanceThreshold 的路
  • 题目要找出一个城市，它到达其他城市数目最少
    • 若有多个到达数量一样少的城市，则回传编号最大的

  

• 测资的 Input/Output

  • 有 n 个城市
  • edges 为城市到城市间的路径权重
  • distanceThreshold 类似精力值，你走的路径权重和不得大於 distanceThreshold
  • 回传能够抵达最少数量的城市，若有多个这样的情况，则回传编号最大的城市
    • 以范例1为例，city 0 与 city 3 都只能抵达两个城市，则回传编号较大的 city 3
      

• 题目的条件

  • 城市为 2~100 个
  • 路径为 1~ n*(n-1) 条
  • edges 固定为三个一组 [从i点,到j点,的权重]
  • 城市每一点编号为 0 ~ n-1
  • 权重与 distanceThreshold 介於 1~10000 (皆为正数，无负周期)