Checking Existence Of Edge Length Limited Paths - Leetcode Solution

The problem "Checking Existence Of Edge Length Limited Paths" on LeetCode asks for a function that takes as input a graph and a list of queries. Each query consists of two vertices in the graph and a maximum edge length, and the function should return a list of boolean values indicating whether there exists a path between the two vertices in the graph such that the length of all edges on the path is less than or equal to the maximum edge length specified in the query.

The approach to solving this problem involves using a modified version of Dijkstra's algorithm, which is a popular algorithm for finding the shortest path between two vertices in a graph with non-negative edge weights. The modified version of Dijkstra's algorithm takes an additional parameter, namely the maximum edge length allowed for the path.

One way to implement this algorithm is as follows:

1. Define a function to perform Dijkstra's algorithm with a maximum edge length constraint. The function should take as input the graph, the source vertex, and the maximum edge length allowed for the path. The function should return a list of distances from the source vertex to all other vertices in the graph, where any distances greater than the maximum edge length are set to infinity.

2. Define a function to perform the "check" operation for each query. The function should take as input the graph, the source and destination vertices for the query, and the maximum edge length allowed for the path. The function should use the modified version of Dijkstra's algorithm to compute the shortest path between the source and destination vertices such that the length of all edges on the path is less than or equal to the maximum edge length specified in the query. If such a path exists, the function should return True; otherwise, it should return False.

3. Iterate through the list of queries and call the "check" function for each query. The results should be appended to a list, which is returned as the output from the main function.

Here is the Python implementation of the algorithm:

import heapq
from collections import defaultdict

def dijkstra_with_limit(graph, start, limit):
    """
    Compute the shortest path from the start vertex to all other vertices in
    the graph such that the length of all edges on the path is less than or
    equal to the given limit.
    """
    distances = defaultdict(lambda: float('inf'))
    distances[start] = 0
    visited = set()
    heap = [(0, start)]
    
    while heap:
        (current_dist, current_vert) = heapq.heappop(heap)
        if current_vert in visited:
            continue
        visited.add(current_vert)
        for neighbor, weight in graph[current_vert].items():
            if weight > limit:
                continue
            shortest_dist = distances[current_vert] + weight
            if shortest_dist < distances[neighbor]:
                distances[neighbor] = shortest_dist
                heapq.heappush(heap, (shortest_dist, neighbor))
    
    return distances

def check_path_exists(graph, start, end, limit):
    """
    Check whether there exists a path from the start vertex to the end vertex
    in the graph such that the length of all edges on the path is less than or
    equal to the given limit.
    """
    distances = dijkstra_with_limit(graph, start, limit)
    return distances[end] != float('inf')

def edgeLengthLimitedPaths(n, edgeList, queries):
    """
    Main function to solve the problem.
    """
    graph = defaultdict(dict)
    for (u, v, weight) in edgeList:
        graph[u][v] = weight
        graph[v][u] = weight
    
    results = []
    for (u, v, limit) in queries:
        results.append(check_path_exists(graph, u, v, limit))
    
    return results

The main function edgeLengthLimitedPaths takes as input the number of vertices in the graph, a list of edges, and a list of queries. The edges are represented as a list of tuples, where each tuple contains the two vertices and the weight of the edge. The queries are represented as a list of tuples, where each tuple contains the two vertices and the maximum edge length allowed for the path.

The function first converts the list of edges into a dictionary representation of the graph, where each vertex is a key and the value is another dictionary containing the neighbors and their corresponding edge weights.

Then, for each query, the check_path_exists function is called to determine whether there exists a path between the source and destination vertices such that the length of all edges on the path is less than or equal to the maximum edge length specified in the query. The results are stored in a list, which is returned as the final output from the main function.

Overall, the time complexity of the algorithm is O(Q(VlogV+E)), where Q is the number of queries, V is the number of vertices in the graph, and E is the number of edges in the graph. This is because the algorithm performs a modified version of Dijkstra's algorithm for each query, where the time complexity is O(VlogV+E). The space complexity of the algorithm is O(V+E), which is the space required to represent the graph using a dictionary.

1