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:

1. 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.

2. Visited Set: A list called vis is created with a size of n + 1, where n is the number of cities. The list is initialized with False 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.

3. Distance Initialization: A variable ans is initialized with inf (infinity). This variable is used to keep track of the minimum distance encountered on any path between city 1 and city n.

4. 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 distance d of the current city i.
   • We update ans with the minimum of its current value and d each time we encounter a smaller distance.
   • If the neighbor j has not yet been visited (vis[j] is False), we mark it as visited by setting vis[j] to True and then recursively call dfs(j) to continue exploring the graph from city j.

5. Starting the DFS Traversal: We call dfs(1) to begin our DFS traversal from city 1. This will explore different paths to reach city n.

6. 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 city n. This ans 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:

1. Graph Representation: We first convert the roads array to a graph represented as a defaultdict 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.

2. Visited Set: We create vis = [False, False, False, False, False].

3. Distance Initialization: Set ans = inf.

4. DFS Algorithm: For the dfs function, starting with dfs(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, so ans becomes 2.
       • City 4 has no unvisited neighbors left, so DFS goes back up.

   This process continues until all possible paths between city 1 and city 4 have been explored through recursion.

5. 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 takes O(E) time where E 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), where E is the number of edges.

• Visited Array: This is an array of length n + 1, thus taking up O(V) space where V 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.