iT邦幫忙

2021 iThome 鐵人賽

DAY 25
1
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 25

【第二十五天 - Floyd-Warshall 題目分析】

  • 先簡單回顧一下,今天預計分析的題目:

  • 題目連結: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 權重的路
    • 題目要找出一個城市,它到達其他城市數目最少
      • 若有多個到達數量一樣少的城市,則回傳編號最大的
        https://ithelp.ithome.com.tw/upload/images/20210925/20140592QrxbSPziTC.png
  • 測資的 Input/Output

    • 有 n 個城市
    • edges 為城市到城市間的路徑權重
    • distanceThreshold 類似精力值,你走的路徑權重和不得大於 distanceThreshold
    • 回傳能夠抵達最少數量的城市,若有多個這樣的情況,則回傳編號最大的城市
      • 以範例1為例,city 0 與 city 3 都只能抵達兩個城市,則回傳編號較大的 city 3
        https://ithelp.ithome.com.tw/upload/images/20210925/201405925AypWYf2tV.png

    首先利用 Floyd-Warshall 計算任兩城市間的最短路徑長。此處建立 distance 陣列用以紀錄 DP 狀態

    • 初始狀態:
      • 不經過任何中繼站時,任兩點的距離。
      • 若無法到達目的地,則距離為無限大。
    # Initialize
    distance = [ [ float('inf') ] * n for i in range(n) ]
    for i in range(n): distance[i][i] = 0
    for i in edges: 
        distance[i[0]][i[1]] = i[2] 
        distance[i[1]][i[0]] = i[2] 
    
    • 開始計算 Floyd-Warshall,不斷更新 distance
    # Floyd-Warshall
    for i in range(n):
        for j in range(n):
            for k in range(n):
                distance[j][k] = min(distance[j][i] + distance[i][k], distance[j][k])
    
    • 最後統計每個城市可以抵達的其他城市,找出數量最少者
    # Count Neighbor
    countNeighbor = [len(list(filter(lambda x: x <= distanceThreshold, distance[i]))) - 1 for i in range(n)]
    return min(range(n), key=lambda x: (countNeighbor[x], -x))
    
    • 完整程式碼如下:
    class Solution:
        def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
            # Initialize
    				distance = [ [ float('inf') ] * n for i in range(n) ]
            for i in range(n): distance[i][i] = 0
            for i in edges: 
                distance[i[0]][i[1]] = i[2] 
                distance[i[1]][i[0]] = i[2] 
    
            # Floyd-Warshall
            for i in range(n):
                for j in range(n):
                    for k in range(n):
                        distance[j][k] = min(distance[j][i] + distance[i][k], distance[j][k])
    
    				# Count Neighbor
            countNeighbor = [len(list(filter(lambda x: x <= distanceThreshold, distance[i]))) - 1 for i in range(n)]
            return min(range(n), key=lambda x: (countNeighbor[x], -x))
    

上一篇
【第二十四天 - Floyd-Warshall介紹】
下一篇
【第二十六天 - Dijkstra 介紹】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言