There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold.
Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.
Notice that the distance of a path connecting cities i and j is equal to the sum of the edges' weights along that path.
Example 1:
Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 Output: 3 Explanation: The figure above describes the graph. The neighboring cities at a distanceThreshold = 4 for each city are: City 0 -> [City 1, City 2] City 1 -> [City 0, City 2, City 3] City 2 -> [City 0, City 1, City 3] City 3 -> [City 1, City 2] Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.
Example 2:
Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2 Output: 0 Explanation: The figure above describes the graph. The neighboring cities at a distanceThreshold = 2 for each city are: City 0 -> [City 1] City 1 -> [City 0, City 4] City 2 -> [City 3, City 4] City 3 -> [City 2, City 4] City 4 -> [City 1, City 2, City 3] The city 0 has 1 neighboring city at a distanceThreshold = 2.
Constraints:
2 <= n <= 1001 <= edges.length <= n * (n - 1) / 2edges[i].length == 30 <= fromi < toi < n1 <= weighti, distanceThreshold <= 10^4(fromi, toi) are distinct.The Floyd-Warshall algorithm is a classical dynamic programming algorithm to solve the all-pairs shortest path problem. It works well for graphs that have both weighted and unweighted edges. The algorithm iteratively updates the distance matrix for each possible intermediate node and provides the shortest distances between any two nodes.
The algorithm has a time complexity of O(n^3) and a space complexity of O(n^2), making it suitable for graphs with up to 100 nodes as given in the problem constraints.
This solution implements the Floyd-Warshall algorithm to compute shortest paths between all city pairs. It then counts the number of neighboring cities within the given distance threshold for each city and identifies the city with the smallest number of reachable neighbors.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3), where n is the number of cities.
Space Complexity: O(n^2) for storing the distance matrix.
Dijkstra's Algorithm can be employed to find the shortest path from one city to another in a graph with non-negative weights. We can utilize this algorithm to determine the shortest distance from every city to all other cities consecutively, assessing the count of reachable cities within the threshold afterward.
This solution leverages Dijkstra's algorithm separately on each city to compute all pairs shortest distance, and subsequently determines the smallest neighbors count within a specific threshold.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) for each node multiplied by n trips resulting in O(n^3).
Space Complexity: O(n^2) for graph storage.
| Approach | Complexity |
|---|---|
| Floyd-Warshall Algorithm | Time Complexity: |
| Dijkstra's Algorithm | Time Complexity: |
G-43. Find the City With the Smallest Number of Neighbours at a Threshold Distance • take U forward • 98,792 views views
Watch 9 more video solutions →Practice Find the City With the Smallest Number of Neighbors at a Threshold Distance with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor