2065. Maximum Path Quality of a Graph


Problem Description

The problem presents an undirected graph consisting of nodes numbered from 0 to n - 1. Each node has an associated value provided in the array values, where values[i] represents the value of the ith node. The graph also contains edges described in the edges array, with each entry [u, v, time] indicating an undirected edge connecting nodes u and v that requires time seconds to traverse. You are also given a time constraint, maxTime.

Your task is to determine the maximum "quality" of any loop path in the graph that starts and ends at node 0 and does not take more than maxTime seconds to complete. The quality of a path is defined as the sum of the values of unique nodes visited within the path, each node's value being counted only once. The graph is restricted so that each node has at most four connecting edges.

Intuition

To arrive at the solution, we need to consider each possible path that starts and ends at Node 0 and calculate its quality, ensuring that the total time taken for each path is within the maxTime limit. This is a classic graph traversal problem, complicated by the need to keep track of the time spent and maximize the sum of node values along the path.

To explore all possible paths efficiently, a depth-first search (DFS) algorithm can be used. We use a recursive approach to explore all possible paths, starting from node 0. As we traverse, we maintain a record of nodes already visited to avoid counting the same node's value more than once, and we keep track of the remaining time after each edge traversal.

When the start node (node 0) is reached again, we compare the current path's quality to the maximum quality found thus far and store the larger one. To make this process efficient, the recursive DFS approach allows us to go back ("backtrack") and explore alternate paths by marking nodes as unvisited after exploring paths through them. Doing so lets us explore all possible paths from the starting node without unnecessarily repeating any paths.

The algorithm ensures that it only considers valid paths by using the remaining time as a guard in the recursive function. If a move to an adjacent node will result in a negative remaining time, that path is not explored further. This optimization is crucial for the algorithm to remain efficient and practical, especially in dense graphs with many edges.

The use of DFS and backtracking allows us to explore all viable paths to find the one that yields the maximum quality within the given time constraint, effectively solving the problem.

Solution Approach

The solution traverses the graph using a Depth-First Search (DFS) algorithm to explore all possible paths from node 0 within the time constraint maxTime. The algorithm specifically involves the following steps:

  1. Preprocessing Stage:

    • Initialize a graph g which is an adjacency list where each g[u] contains a list of adjacent nodes v and the time t needed to travel to that node. This structure allows for quick access to all possible moves from any node.
    • Create an array visited to keep track of which nodes have been visited on the current path, preventing multiple counts of the same node's value.
  2. DFS Function:

    • This recursive function dfs(u, time, value) takes the current node u, the remaining time time, and the accumulated value of the path value as parameters.
    • It first checks if the current node is the starting node (node 0) and updates the answer ans if the current accumulated value is greater than the previously recorded maximum.
    • Then, it iterates over all adjacent nodes of u. For each neighbor v, if enough time is remaining to travel on the edge (u,v):
      • If v has not yet been visited, mark v as visited and recurse with the reduced remaining time and increased path value.
      • If v has been visited, recurse with the reduced remaining time but without increasing the path value.
    • After exploring all paths from node v, we reset the visited[v] to false to allow other paths to consider v as a part of their route. This is the backtracking step, which is crucial to explore all unique paths in the graph.
  3. Handling the Start:

    • Before starting the DFS traversal, the start node (node 0) is marked as visited, and the dfs function is called with node 0, the full time maxTime, and the initial value values[0].

The DFS traversal ensures that all potential paths are explored, and the visited array combined with the checking of time ensures that the solution is optimized by only considering valid paths. The backtracking element ensures that after exploring each path, the program can revert changes and try a new path, which is essential for covering all unique combinations of nodes within the time constraint.

When the DFS process is complete, the maximum quality ans will hold the highest value calculated for any valid path that starts and ends at node 0 and respects the maxTime limit. The efficient use of recursion, backtracking, and adjacency list for the graph representation all contribute to the solution's effectiveness.

Example Walkthrough

Let's go through an example to illustrate the solution approach with a small graph.

Suppose we have the following input:

  • n = 4 (four nodes numbered 0 to 3)
  • values = [1, 2, 3, 4] (values associated with each node)
  • edges = [[0, 1, 2], [1, 2, 1], [2, 0, 3], [1, 3, 2], [3, 0, 4]] (edges with associated travel times)
  • maxTime = 6 (maximum allowed time to complete the loop path)

Let's visualize the graph:

10 --(2)-- 1 --(2)-- 3 --(4)-- 0
2 \                       /
3  \                     /
4  (3)                 (1)
5    \                 /
6     \               /
7       --(1)-- 2 ---

Preprocessing Stage:

We construct our adjacency list as follows:

  • g[0] = [(1, 2), (2, 3)]
  • g[1] = [(0, 2), (2, 1), (3, 2)]
  • g[2] = [(0, 3), (1, 1)]
  • g[3] = [(1, 2), (0, 4)] And we initialize our visited array to [false, false, false, false].

DFS Function:

Before starting the DFS, we mark node 0 as visited (visited[0] = true) and start the DFS with dfs(0, 6, 1).

  1. We start at node 0. Since it is the start node and we have only been to node 0, we don't need to update ans.
  2. From node 0, we can move to node 1 spending 2 seconds. We now call dfs(1, 4, 3). We have 4 seconds remaining, and the path value is now 3 (1+2 because we visited a new node).
  3. From node 1, we move to node 2 spending 1 second. We call dfs(2, 3, 6). We have 3 seconds remaining, and the path value is 6 (1+2+3).
  4. From node 2, we can only move back to node 0 as moving to 1 would have no effect on the value (since it has already been visited). We take the edge (2, 0) spending 3 seconds and call dfs(0, 0, 6). We have 0 seconds remaining, and we reached back to the start node, so we update ans = 6.

At this point, we backtrack to try different paths:

  • We move back up to node 1 and try moving to node 3, which spends 2 seconds. We can't go from node 1 to node 3, as we won't have enough time to return to node 0.
  • Thus, node 1 can't explore any more paths, and we backtrack further to node 0.

Now, let's consider a different path from node 0:

  • From node 0, we can take the (0, 2) edge spending 3 seconds and then move from 2 to 1 and back to 0.

By exploring all possible paths with the remaining time while avoiding revisiting the nodes and backtracking after each exploration, we ensure exhaustive coverage of all valid loop paths starting and ending at node 0. After the DFS process is complete and all possible paths have been explored, with each valid path contributing to the update of ans, the final value of ans, which in this example is 6, is our maximum quality for any loop path within maxTime.

Python Solution

1from typing import List, Tuple
2
3# Define a graph as a type for better clarity
4Graph = List[List[Tuple[int, int]]]
5
6# Function to find the maximal path quality
7def maximal_path_quality(values: List[int], edges: List[List[int]], max_time: int) -> int:
8    num_nodes = len(values)
9    graph: Graph = [[] for _ in range(num_nodes)]
10
11    # Populate the adjacency list for the graph
12    for edge in edges:
13        from_node, to_node, time = edge
14        graph[from_node].append((to_node, time))
15        graph[to_node].append((from_node, time))
16
17    # List to keep track of visited nodes
18    visited = [False] * num_nodes
19    max_quality = 0
20
21    # DFS function to explore paths
22    def dfs(current_node: int, remaining_time: int, current_quality: int) -> None:
23        nonlocal max_quality
24
25        # If we've reached the start again, consider the value of this path
26        if current_node == 0:
27            max_quality = max(current_quality, max_quality)
28      
29        # Recursive exploration of neighbors
30        for next_node, travel_time in graph[current_node]:
31            if remaining_time - travel_time >= 0:
32                if not visited[next_node]:
33                    visited[next_node] = True
34                    dfs(next_node, remaining_time - travel_time, current_quality + values[next_node])
35                    # Backtrack
36                    visited[next_node] = False
37                else:
38                    dfs(next_node, remaining_time - travel_time, current_quality)
39
40    # Start from node 0
41    visited[0] = True
42    dfs(0, max_time, values[0])
43
44    return max_quality
45
46# Usage example (Uncomment to test the function):
47# values = [0, 32, 10, 43]
48# edges = [[0, 1, 10], [1, 2, 15], [0, 3, 10]]
49# max_time = 49
50# result = maximal_path_quality(values, edges, max_time)
51# print(result)  # Output should be the maximum path quality within the given maxTime
52

Java Solution

1import java.util.ArrayList;
2import java.util.List;
3
4// A class for representing the graph and performing DFS to find the maximal path quality
5public class PathQualityFinder {
6
7    // Graph represented as an adjacency list, where graph[node] contains pairs of neighbor node and traveling time
8    private List<List<Pair<Integer, Integer>>> graph;
9
10    // The maximum quality found during DFS
11    private int maxQuality;
12
13    // Discovered states of nodes to avoid revisiting
14    private boolean[] visited;
15
16    // Constructor to create and initialize the graph from the edges
17    public PathQualityFinder(int numNodes, int[][] edges) {
18        graph = new ArrayList<>(numNodes);
19        for (int i = 0; i < numNodes; i++) {
20            graph.add(new ArrayList<>());
21        }
22        // Build the graph from the edge list
23        for (int[] edge : edges) {
24            int from = edge[0];
25            int to = edge[1];
26            int time = edge[2];
27            graph.get(from).add(new Pair<>(to, time));
28            graph.get(to).add(new Pair<>(from, time));
29        }
30    }
31
32    // Method for finding the maximal path quality
33    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
34        int numNodes = values.length;
35        this.visited = new boolean[numNodes];
36        this.maxQuality = 0;
37
38        // Start DFS from the node 0
39        visited[0] = true;
40        dfs(0, maxTime, values[0], values);
41
42        return maxQuality;
43    }
44
45    // Helper method for Depth-First Search (DFS)
46    private void dfs(int currentNode, int remainingTime, int currentQuality, int[] values) {
47        // If we've reached the start again, update the maximum path quality
48        if (currentNode == 0 && currentQuality > maxQuality) {
49            maxQuality = currentQuality;
50        }
51
52        // Recursively visit neighbors
53        for (Pair<Integer, Integer> nextPair : graph.get(currentNode)) {
54            int nextNode = nextPair.getKey();
55            int travelTime = nextPair.getValue();
56
57            if (remainingTime - travelTime >= 0) {
58                // Try to visit the next node, if we haven't yet
59                if (!visited[nextNode]) {
60                    visited[nextNode] = true;
61                    dfs(nextNode, remainingTime - travelTime, currentQuality + values[nextNode], values);
62                    visited[nextNode] = false; // Backtrack
63                } else {
64                    // Recursively visit the next node, even if it was visited before
65                    dfs(nextNode, remainingTime - travelTime, currentQuality, values);
66                }
67            }
68        }
69    }
70
71    // Utility class for storing pairs of integers
72    static class Pair<K, V> {
73        private K key;
74        private V value;
75
76        public Pair(K key, V value) {
77            this.key = key;
78            this.value = value;
79        }
80
81        public K getKey() {
82            return key;
83        }
84
85        public V getValue() {
86            return value;
87        }
88    }
89
90    // Main method for testing the functionality (optional)
91    public static void main(String[] args) {
92        int[] values = {0, 32, 10, 43};
93        int[][] edges = {{0, 1, 10}, {1, 2, 15}, {0, 3, 10}};
94        int maxTime = 49;
95
96        PathQualityFinder finder = new PathQualityFinder(values.length, edges);
97        int result = finder.maximalPathQuality(values, edges, maxTime);
98        System.out.println(result); // Output should be the maximum path quality within the given maxTime
99    }
100}
101

C++ Solution

1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6// Graph is represented as a vector of vectors of pairs,
7// where each pair is a node index and the time it takes to reach it.
8using Graph = vector<vector<pair<int, int>>>;
9
10// Function to find the maximal path quality
11int maximalPathQuality(const vector<int>& values, const vector<vector<int>>& edges, int maxTime) {
12    const int numNodes = values.size();
13    Graph graph(numNodes);
14
15    // Populate the adjacency list for the graph
16    for (const auto& edge : edges) {
17        int from = edge[0];
18        int to = edge[1];
19        int time = edge[2];
20        graph[from].emplace_back(to, time);
21        graph[to].emplace_back(from, time);
22    }
23
24    // Vector to keep track of visited nodes
25    vector<bool> visited(numNodes, false);
26    int maxQuality = 0;
27
28    // Depth-First Search (DFS) to explore paths
29    function<void(int, int, int)> dfs = [&](int currentNode, int remainingTime, int currentQuality) {
30        // If we've reached the start again, update maximum path quality
31        if (currentNode == 0) {
32            maxQuality = max(currentQuality, maxQuality);
33        }
34
35        // Recursive exploration of neighbors
36        for (const auto& [nextNode, travelTime] : graph[currentNode]) {
37            if (remainingTime - travelTime >= 0) {
38                if (!visited[nextNode]) {
39                    visited[nextNode] = true;
40                    dfs(nextNode, remainingTime - travelTime, currentQuality + values[nextNode]);
41                    visited[nextNode] = false; // Backtrack
42                } else {
43                    dfs(nextNode, remainingTime - travelTime, currentQuality);
44                }
45            }
46        }
47    };
48
49    // Starting from node 0
50    visited[0] = true;
51    dfs(0, maxTime, values[0]);
52
53    return maxQuality;
54}
55
56// Usage example:
57/* int main() {
58    vector<int> values = {0, 32, 10, 43};
59    vector<vector<int>> edges = {{0, 1, 10}, {1, 2, 15}, {0, 3, 10}};
60    int maxTime = 49;
61    int result = maximalPathQuality(values, edges, maxTime);
62    cout << result << endl; // Output should be the maximum path quality within the given maxTime
63    return 0;
64} */
65

Typescript Solution

1// Global variables and functions - no class definition
2
3// Define a graph type for better clarity
4type Graph = Array<Array<[number, number]>>;
5
6// Function to find the maximal path quality
7function maximalPathQuality(values: number[], edges: number[][], maxTime: number): number {
8    const numNodes = values.length;
9    let graph: Graph = Array.from({ length: numNodes }, () => []);
10
11    // Populate the adjacency list for the graph
12    for (let edge of edges) {
13        let [from, to, time] = edge;
14        graph[from].push([to, time]);
15        graph[to].push([from, time]);
16    }
17
18    // Array to keep track of visited nodes
19    let visited = new Array(numNodes).fill(false);
20    let maxQuality = 0;
21
22    // Depth-First Search (DFS) to explore paths
23    function dfs(currentNode: number, remainingTime: number, currentQuality: number): void {
24        // If we've reached the start again, consider the value of this path
25        if (currentNode === 0) {
26            maxQuality = Math.max(currentQuality, maxQuality);
27        }
28        // Recursive exploration of neighbors
29        for (let [nextNode, travelTime] of graph[currentNode]) {
30            if (remainingTime - travelTime >= 0) {
31                if (!visited[nextNode]) {
32                    visited[nextNode] = true;
33                    dfs(nextNode, remainingTime - travelTime, currentQuality + values[nextNode]);
34                    visited[nextNode] = false; // Backtrack
35                } else {
36                    dfs(nextNode, remainingTime - travelTime, currentQuality);
37                }
38            }
39        }
40    }
41
42    // Starting from node 0
43    visited[0] = true;
44    dfs(0, maxTime, values[0]);
45
46    return maxQuality;
47}
48
49// Usage example (to test the function, remove this if not needed):
50// const values = [0, 32, 10, 43];
51// const edges = [[0, 1, 10], [1, 2, 15], [0, 3, 10]];
52// const maxTime = 49;
53// const result = maximalPathQuality(values, edges, maxTime);
54// console.log(result); // Output should be the maximum path quality within the given maxTime
55

Time and Space Complexity

Time Complexity

The time complexity of the given code is primarily determined by the depth-first search function dfs. For each node u, dfs is called, and it recursively explores all the paths until maxTime is exhausted. In the worst-case scenario, every path from the starting node to all other nodes has to be checked, which could be exponential in nature due to the possibility of revisiting nodes along different paths (except that a visited node with a current path's value addition will not be revisited in that path).

Given that n is the number of vertices (nodes) and e is the number of edges in the graph, the dfs function in the worst case could visit all possible paths in a fully connected graph. Since vertices can be revisited along different paths, the time complexity is O(n * (2^n)), as there could be n choices at the first level, 2^n - 1 at the second level down to the nth level due to binary choices of visiting or not visiting an already visited node.

Another aspect of the time complexity comes from the for-loop that iterates over the adjacency list of each node, which contributes to O(e), thus making the time complexity O(e + n * (2^n)), which simplifies to O(n * (2^n)) as 2^n grows faster than e for large values of n.

Space Complexity

The space complexity of the code is determined by the storage of the graph structure, the recursive call stack depth, and the visited array.

  1. Graph Representation (g): Since it's an adjacency list, the space complexity would be O(n + e), where n is the number of nodes and e is the number of edges.
  2. Visited Array: Uses O(n) space.
  3. Recursive Call Stack: In the worst case, the call stack would grow to O(n) when exploring a path that traverses all nodes.

Thus, the overall space complexity combines these factors, resulting in O(n + e) + O(n) + O(n), which simplifies to O(n + e) as both n and e terms are linear, and the largest one will dominate the space complexity.


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.


TA 👨‍🏫