# Maximum Path Quality of a Graph

##### February 4, 2024

## 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**:

- 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 #

- Build a graph from the
`edges`

array. - Use DFS to explore all paths starting from node
`0`

, accumulate values, and track the time spent. - If the current path exceeds
`maxTime`

, stop exploring further. - Each time node
`0`

is revisited, add its value to the total quality. - Keep track of the maximum quality found during the traversal.
- 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.