Maximum Path Quality of a Graph

Maximum Path Quality of a Graph

February 4, 2024
medium
Graphs, DFS

Problem Statement #

Given a weighted undirected graph with n vertices numbered from 0 to n-1, represented by an array edges where edges[i] = [from_i, to_i, weight_i] denotes a bidirectional and weighted edge between nodes from_i and to_i. Each node has a value values[i] representing its value. You start traversing the graph from node 0 and collect values. You can visit each node at most once. However, you can revisit node 0 any number of times. A path’s quality is the sum of the values of the visited nodes, including node 0 every time it is visited. You are also given an integer maxTime. Return the maximum quality of a path where the total time spent on the path does not exceed maxTime.

Example:

  1. Input: values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49 Output: 75 Explanation: The path to take is 0 -> 1 -> 0 -> 3, which has a quality of 0 + 32 + 0 + 43 = 75.

Solution Approach #

The solution involves using Depth-First Search (DFS) to traverse all possible paths while tracking the total time and quality.

Algorithm Steps #

  1. Build a graph from the edges array.
  2. Use DFS to explore all paths starting from node 0, accumulate values, and track the time spent.
  3. If the current path exceeds maxTime, stop exploring further.
  4. Each time node 0 is revisited, add its value to the total quality.
  5. Keep track of the maximum quality found during the traversal.
  6. Return the maximum quality after exploring all paths.

Code (Python) # 

def maxPathQuality(values, edges, maxTime):
    graph = {i: [] for i in range(len(values))}
    for u, v, time in edges:
        graph[u].append((v, time))
        graph[v].append((u, time))

    def dfs(node, time, quality):
        if time > maxTime: return 0
        returnQuality = quality + values[0] if node == 0 else quality
        maxQuality = returnQuality
        for next_node, edge_time in graph[node]:
            maxQuality = max(maxQuality, dfs(next_node, time + edge_time, returnQuality))
        return maxQuality

    return dfs(0, 0, 0)

# Example usage
values = [0,32,10,43]
edges = [[0,1,10],[1,2,15],[0,3,10]]
maxTime = 49
print(maxPathQuality(values, edges, maxTime))  # Output: 75

Time Complexity #

O(V+E), where V is the number of vertices and E is the number of edges in the graph. In the worst case, DFS explores every vertex and edge.

Space Complexity #

O(V), for the recursion stack and graph representation.