We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Shortest Path with K Hops

Number: 2865

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

You are given an undirected weighted connected graph with n nodes (0-indexed) and an edge list. Additionally, you are provided with two nodes s and d, and a positive integer k. The objective is to determine the shortest path from s to d when you are allowed to set the weight of at most k edges used in the path to 0.

Key Insights

  • The problem is a variant of the traditional shortest path but with an extra twist: you can “hop” over (set weight = 0) on at most k edges.
  • Each state in the traversal is defined by (current_node, hops_used) because the cost and the possibility to hop further depends on how many hops are already used.
  • We can use a modified Dijkstra’s algorithm, where each node can have multiple states based on the number of hops used so far.
  • We maintain a distance table indexed by (node, hops_used) and use a min-priority queue (heap) for exploring the best current option.
  • The two options at every edge are: traverse normally (adding the weight) or hop (if hops available) and add 0 cost.

Space and Time Complexity

Time Complexity: O((V + E) * k * log(V * k)) – since every state (node, hops_used) is processed using a priority queue. Space Complexity: O(V * k) – storing the distance for each node for different hops used.

Solution

We solve the problem using a modified Dijkstra’s algorithm that incorporates the number of hops used as an extra dimension in the state. For every state (current_node, hops_used) reached with some cost, we evaluate each adjacent edge in two ways:

  1. Without hopping: the new cost is the current cost plus the edge’s weight, and the hops_used remains unchanged.
  2. With hopping (if hops_used is less than k): the new cost remains unchanged (edge weight becomes 0), and hops_used is incremented by 1.

A min-heap is used to always expand the state with the smallest current cost. When we reach the destination, we can return the minimum cost.

Code Solutions

import heapq

def findShortestPathWithKHops(n, edges, s, d, k):
    # Build adjacency list for the undirected graph
    graph = {i: [] for i in range(n)}
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # dist[node][hops_used] stores the shortest distance to reach node with hops_used hops applied
    dist = [[float('inf')] * (k + 1) for _ in range(n)]
    dist[s][0] = 0
    
    # Heap contains tuple: (current_distance, current_node, hops_used)
    heap = [(0, s, 0)]
    
    while heap:
        curr_dist, node, hops_used = heapq.heappop(heap)
        
        # Early exit if destination key is reached
        if node == d:
            return curr_dist
        
        # Skip if this state is outdated
        if curr_dist > dist[node][hops_used]:
            continue
        
        # Explore neighbors
        for neighbor, weight in graph[node]:
            # Option 1: Traverse normally
            new_dist = curr_dist + weight
            if new_dist < dist[neighbor][hops_used]:
                dist[neighbor][hops_used] = new_dist
                heapq.heappush(heap, (new_dist, neighbor, hops_used))
            # Option 2: Hop (set weight to 0) if hops remain
            if hops_used < k:
                new_dist = curr_dist  # weight becomes 0
                if new_dist < dist[neighbor][hops_used + 1]:
                    dist[neighbor][hops_used + 1] = new_dist
                    heapq.heappush(heap, (new_dist, neighbor, hops_used + 1))
    # Return minimum among all possible hop states for destination
    return min(dist[d])

# Example usage:
n = 4
edges = [[0,1,4], [0,2,2], [2,3,6]]
s = 1
d = 3
k = 2
print(findShortestPathWithKHops(n, edges, s, d, k))  # Expected output: 2
← Back to All Questions