leetcode-graph

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance.py

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        """    
        It's all pairs shortest path problems.
        
        Given an undirected and weighted graph with n nodes and path distance threshold, find the city with the smallest number of cities.
        
        Step1: We can simply use Floyd-Warshall algorithm to find the minium distance any two cities.(we need shortest path between any two nodes ih the graph)
        Step2: Calculate number for each city that this city can reach satisfying distance threshold
        Step3: Return city with fewest number from itself to others city and wi
        
        T:O(n^3)
        S:O(n^2) for two-dimensional distances array
        
        Idea of Floyd-Warshall algorithm:
        
        iterate all intermediate node k,
            iterate all pairs (i,j),
                update dist from node i to node j when dist from i to k + dist from k to j is less than it.
        """
        # Initallly, all distances amonng each nodes are infinite.
        distances = [[float('inf') for _ in range(n)] for _ in range(n)]
        for i in range(n):
            # the distance from each node to itself is 0.(the diagonal element is zero)
            distances[i][i] = 0
        for i, j, w in edges:
            # the distance from node a to node b is the weight if there's an edge.
            distances[i][j] = distances[j][i] = w # undirected graph
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    # take the k as the immediate node, and compare length of path i->J with i->k->j and take the minimum out of them as shorter distance from node i to node j.
                    distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])
        
        # 收尾刀 for this problem
        num_city_map = {}
        for i in range(n):
            c = 0
            for d in distances[i]:
                if 0 < d <= distanceThreshold: 
                    c += 1
            # override the index of node when they have same number of citiess that are reachable.
            num_city_map[c] = i
        return num_city_map[min(num_city_map)]