2492. Minimum Score of a Path Between Two Cities
Problem Description
In this problem, we are working with a graph that represents a system of cities and bidirectional roads connecting these cities. The graph is composed of n
cities, which are numbered from 1 to n
. The roads are represented by a 2D array roads
, where each element in the array is a trio [a, b, distance]
. This trio indicates that there is a road connecting city a
and city b
with a distance of distance
. It's important to note that the graph of cities may not be fully connected, meaning some cities may not have a direct path to others.
The "score" of a path in this graph is a little unique; rather than summing up the total distance or considering average distance, the score is defined as the minimum distance of any road in that particular path. Put another way, out of all the roads used in a path, the score is the distance of the shortest one among them.
Our goal is to determine the minimum possible score of a path between city 1 and city n
. A few rules apply to paths:
- A path is simply a sequence of roads connecting two cities; it may pass through intermediate cities.
- It is permissible for a path to include the same road more than once, if necessary.
- You can go through cities 1 and
n
multiple times to find the path with the optimal score. - There is at least one path between city 1 and city
n
in all test cases.
Ultimately, we want to compute the highest "weakest" road in the best path from city 1 to city n
.
Intuition
To solve this problem, we can utilize Depth-First Search (DFS) to explore all possible paths from city 1 to city n
. As we perform DFS, we track the minimum distance encountered along the current path. Before starting DFS, we initialize the answer ans
with a value representing infinity (inf
), because we will be minimizing this score as we go along.
To apply DFS, we first create a defaultdict
of lists called g
, which will be our graph where the keys are city numbers and the values are lists of tuples representing connected cities alongside the respective distances. We also create a list vis
of boolean values, initialized to False
, that keeps track of the cities that have been visited to prevent revisiting them in the current path exploration.
Our DFS process named dfs()
takes a city i
as an argument and iterates through all of its connections. For each adjacent city j
with distance d
to city i
, we minimize ans
with d
to find the smallest distance seen so far along this path segment. We also mark j
as visited and perform DFS from j
. The process recursively continues until we have exhausted all possible paths.
After initializing our data structures, we simply call dfs(1)
to start from the first city and allow the DFS to explore paths until city n
. Once DFS is done, the ans
variable will hold the minimum score among all paths from city 1 to city n
.
The solution is neat because it elegantly uses DFS to explore the space of paths, and it cleverly updates the minimum score on-the-fly. It relies on the fact that, since the score is the minimum distance along a path, we just need to track the smallest road distance encountered at any point in our DFS exploration.
Solution Approach
The implementation of the solution utilizes a Depth-First Search (DFS) algorithm which is a common strategy for exploring all the vertices of a graph. Let us walk through the important points of the implementation:
-
Graph Representation: A
defaultdict
of lists is used to represent the graph (g
). Each key in the defaultdict represents a city, and the value is a list of tuples. Each tuple consists of a destination city and the distance to that city. This allows us to easily iterate over all neighbors of a city. -
Visited Set: A list called
vis
is created with a size ofn + 1
, wheren
is the number of cities. The list is initialized withFalse
to indicate that no city has been visited at the start. This ensures that we do not enter into an infinite loop by revisiting cities during our DFS traversal. -
Distance Initialization: A variable
ans
is initialized withinf
(infinity). This variable is used to keep track of the minimum distance encountered on any path between city 1 and cityn
. -
DFS Algorithm: A recursive function
dfs(i)
is defined, which is responsible for traversing the graph:- Inside the DFS function, we iterate over each neighbor
j
and its associated distanced
of the current cityi
. - We update
ans
with the minimum of its current value andd
each time we encounter a smaller distance. - If the neighbor
j
has not yet been visited (vis[j]
isFalse
), we mark it as visited by settingvis[j]
toTrue
and then recursively calldfs(j)
to continue exploring the graph from cityj
.
- Inside the DFS function, we iterate over each neighbor
-
Starting the DFS Traversal: We call
dfs(1)
to begin our DFS traversal from city 1. This will explore different paths to reach cityn
. -
Result: Given that there is at least one path from city 1 to city
n
, by the end of DFS traversal,ans
will contain the minimum possible score (which is the minimum distance of the weakest road) in some path between city 1 and cityn
. Thisans
is then returned as a result.
The clever use of DFS allows for an efficient search through all the paths while keeping track of the minimum distance encountered, therefore the weakest link in terms of road distance, which effectively determines the score of the path.
Example Walkthrough
Let's illustrate the solution approach with a small example where n = 4
representing four cities and roads
as [[1, 2, 4], [2, 3, 3], [3, 4, 2], [1, 3, 6]]
. This setup implies the following connections:
- City 1 and city 2 are connected by a road with a distance of 4.
- City 2 and city 3 are connected by a road with a distance of 3.
- City 3 and city 4 are connected by a road with a distance of 2.
- City 1 and city 3 are directly connected as well with a distance of 6.
Following our solution approach:
-
Graph Representation: We first convert the
roads
array to a graph represented as adefaultdict
of lists,g
, so that we have:1g = { 2 1: [(2, 4), (3, 6)], 3 2: [(1, 4), (3, 3)], 4 3: [(2, 3), (4, 2), (1, 6)], 5 4: [(3, 2)] 6}
Each list contains tuples that represent connections to neighboring cities and the distance to them.
-
Visited Set: We create
vis = [False, False, False, False, False]
. -
Distance Initialization: Set
ans = inf
. -
DFS Algorithm: For the
dfs
function, starting withdfs(1)
:- Look at neighbors of city 1: (2, 4) and (3, 6).
- For neighbor (2, 4), since city 2 is not visited, mark it visited and compare
ans
with 4.ans
becomes min(inf
, 4) = 4. - Continue DFS by calling
dfs(2)
.- In
dfs(2)
, iterate over neighbors: (1, 4) and (3, 3). - Skip city 1 since it's visited; for city 3 with distance 3, since city 3 is not visited, mark it visited and update
ans
to min(4, 3) = 3. - Continue DFS by calling
dfs(3)
.- In
dfs(3)
, check neighbors (2, 3), (4, 2), and (1, 6). - City 2 is visited, skip. Update
ans
with min(3, 2) when visiting city 4, soans
becomes 2. - City 4 has no unvisited neighbors left, so DFS goes back up.
- In
- In
This process continues until all possible paths between city 1 and city 4 have been explored through recursion.
-
Result: After the DFS is finished,
ans
holds the minimum distance encountered on any path, which in this case is 2. That means the highest "weakest" road on the best path from city 1 to city 4 has a distance of 2. This is the score of our path.
Hence, the minimum possible score for a path between city 1 and city 4 is 2, given this set of roads and cities.
Python Solution
1from collections import defaultdict
2from math import inf # Represents positive infinity
3
4class Solution:
5 def minScore(self, num_nodes: int, roads: List[List[int]]) -> int:
6 # Depth-First Search, where `current_node` is the current node being visited.
7 def dfs(current_node):
8 nonlocal minimum_road_score
9 for neighbor, road_score in graph[current_node]:
10 minimum_road_score = min(minimum_road_score, road_score)
11 if not visited[neighbor]:
12 visited[neighbor] = True
13 dfs(neighbor)
14
15 # Build graph representation from roads input.
16 graph = defaultdict(list)
17 for src, dest, score in roads:
18 graph[src].append((dest, score))
19 graph[dest].append((src, score))
20
21 # Initialize visited nodes list.
22 visited = [False] * (num_nodes + 1)
23
24 # Initialize the answer with infinity.
25 minimum_road_score = inf
26
27 # Start DFS from node 1 (assuming nodes are 1-indexed).
28 visited[1] = True
29 dfs(1)
30
31 # Return the minimum road score found during DFS.
32 return minimum_road_score
33
Java Solution
1class Solution {
2 private List<int[]>[] graph; // Graph represented as adjacency list
3 private boolean[] visited; // Visited array to keep track of visited nodes
4 private int minimumScore = Integer.MAX_VALUE; // Initialize minimum score to maximum possible value
5
6 // Function to find minimum score in the graph
7 public int minScore(int n, int[][] roads) {
8 graph = new List[n]; // Create graph with 'n' nodes
9 visited = new boolean[n]; // Initialize 'visited' array for 'n' nodes
10 // Fill the graph with empty lists for each node
11 Arrays.setAll(graph, k -> new ArrayList<>());
12 // Build the graph from the given roads information
13 for (int[] road : roads) {
14 int from = road[0] - 1; // Convert to 0-indexed
15 int to = road[1] - 1; // Convert to 0-indexed
16 int weight = road[2];
17 // Add edge to the undirected graph
18 graph[from].add(new int[] {to, weight});
19 graph[to].add(new int[] {from, weight});
20 }
21 // Start depth-first search traversal from node 0
22 dfs(0);
23 return minimumScore; // Return the minimum score found during DFS
24 }
25
26 // Helper function to perform depth-first search
27 private void dfs(int currentNode) {
28 // Go through all the connected nodes
29 for (int[] edge : graph[currentNode]) {
30 int nextNode = edge[0]; // Destination node
31 int weight = edge[1]; // Weight of the edge
32 // Update the minimum score encountered so far
33 minimumScore = Math.min(minimumScore, weight);
34 // If the next node is not visited, continue DFS traversal
35 if (!visited[nextNode]) {
36 visited[nextNode] = true; // Mark this node as visited
37 dfs(nextNode); // Recursively call dfs for the next node
38 }
39 }
40 }
41}
42
C++ Solution
1#include <vector>
2#include <climits>
3#include <cstring>
4#include <functional>
5using namespace std;
6
7class Solution {
8public:
9 int minScore(int n, vector<vector<int>>& roads) {
10 // Create an adjacency list to represent the graph
11 vector<vector<pair<int, int>>> graph(n);
12 // Visited array to keep track of visited nodes
13 bool visited[n];
14 // Initialize the visited array to false for all nodes
15 memset(visited, 0, sizeof visited);
16
17 // Populate the adjacency list with road data
18 for (auto& road : roads) {
19 int from = road[0] - 1; // Convert to 0-based index
20 int to = road[1] - 1; // Convert to 0-based index
21 int distance = road[2];
22 graph[from].emplace_back(to, distance);
23 graph[to].emplace_back(from, distance);
24 }
25
26 // Initialize answer to maximum possible value
27 int answer = INT_MAX;
28
29 // Define the depth-first search (DFS) lambda function
30 function<void(int)> dfs = [&](int node) {
31 // Go through all edges connected to the current node
32 for (auto [adj_node, adj_distance] : graph[node]) {
33 // Update answer with the minimum distance so far
34 answer = min(answer, adj_distance);
35 // If adjacent node has not been visited
36 if (!visited[adj_node]) {
37 // Mark as visited
38 visited[adj_node] = true;
39 // Continue DFS from the adjacent node
40 dfs(adj_node);
41 }
42 }
43 };
44
45 // Start DFS from node 0 (converted to 0-based index previously)
46 visited[0] = true; // Mark node 0 as visited
47 dfs(0);
48
49 // Return the minimum score found by DFS
50 return answer;
51 }
52};
53
Typescript Solution
1function minScore(nodeCount: number, edges: number[][]): number {
2 // visited array to keep track of visited nodes
3 const visited = new Array(nodeCount + 1).fill(false);
4 // graph represented by an adjacency list
5 const graph = Array.from({ length: nodeCount + 1 }, () => []);
6
7 // Construct the graph from the given edges
8 for (const [nodeFrom, nodeTo, value] of edges) {
9 graph[nodeFrom].push([nodeTo, value]);
10 graph[nodeTo].push([nodeFrom, value]);
11 }
12
13 // Initialize answer with Infinity to find the minimum value later
14 let minimumScore = Infinity;
15
16 // Depth-first search to traverse the graph and find the minimum edge value
17 const depthFirstSearch = (currentNode: number) => {
18 // If the current node is already visited, skip it
19 if (visited[currentNode]) {
20 return;
21 }
22 // Mark the current node as visited
23 visited[currentNode] = true;
24 // Iterate over all neighbor nodes
25 for (const [nextNode, edgeValue] of graph[currentNode]) {
26 // Update the minimum score with the minimum edge value found so far
27 minimumScore = Math.min(minimumScore, edgeValue);
28 // Continue the search with the next node
29 depthFirstSearch(nextNode);
30 }
31 };
32
33 // Start the DFS from the first node (assuming nodes are labeled starting from 1)
34 depthFirstSearch(1);
35
36 // Return the minimum edge score found during the DFS
37 return minimumScore === Infinity ? -1 : minimumScore; // Return -1 if no edges were found
38}
39
40// Example usage:
41// const score = minScore(4, [[1, 2, 3], [2, 3, 1], [1, 3, 4]]);
42// console.log(score); // Output will be 1 which is the minimum edge value
43
Time and Space Complexity
Time Complexity
The given Python code implements a depth-first search (DFS) on a graph represented as a adjacency list. The dfs
function is called recursively to traverse the graph.
The time complexity of the algorithm depends on the number of nodes n
and the number of edges in the roads
list. The DFS will visit each node exactly once, due to the vis[j] = True
guard before each recursive call.
The complexity can have two major components: the time it takes to set up the adjacency list and the time it takes to do the DFS traversal.
-
Adjacency List Creation: The adjacency list is created by iterating through each road in the
roads
list. This operation takesO(E)
time whereE
is the number of edges as each edge is visited once. -
DFS Traversal: DFS traversal typically has a time complexity of
O(V + E)
for visiting each node and edge at most once.
Therefore the total time complexity is O(V + E)
where V
is the number of vertices and E
is the number of edges.
Space Complexity
The space complexity includes the storage for the graph (adjacency list), the visited array, and the stack space used by the recursive calls of DFS.
-
Graph Storage: Each node stores a list of its edges, so in total this is proportional to
O(E)
, whereE
is the number of edges. -
Visited Array: This is an array of length
n + 1
, thus taking upO(V)
space whereV
is the number of vertices. -
DFS Stack space: In the worst case, the recursive DFS could go as deep as the number of nodes in the graph (imagine a linked-list shaped graph), so the stack space in the worst case can be
O(V)
.
Consequently, the total space complexity is O(E + V)
with consideration for the adjacency list, visited array, and recursive stack space.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.