LeetCode 2714 - Find Shortest Path with K Hops

This problem gives us an undirected weighted graph with n nodes and a list of weighted edges. Each edge connects two nodes and has a positive weight. We are also given a source node s, a destination node d, and an integer k.

leetcodehardgraph-theoryheap-(priority-queue)shortest-path

LeetCode Problem 2714

Difficulty: 🔴 Hard
Topics: Graph Theory, Heap (Priority Queue), Shortest Path

Solution

LeetCode 2714 - Find Shortest Path with K Hops

Problem Understanding

This problem gives us an undirected weighted graph with n nodes and a list of weighted edges. Each edge connects two nodes and has a positive weight. We are also given a source node s, a destination node d, and an integer k.

The goal is to travel from s to d with the minimum possible total cost. However, there is a special ability available: we may choose at most k edges along the path and treat their weight as 0. This operation is called a "hop".

In other words, when traversing an edge, we have two choices:

  1. Travel normally and pay the edge weight.
  2. Use one hop on that edge, making its contribution to the path cost equal to 0.

We may use this special operation at most k times total.

The graph is guaranteed to be connected, which means there is always at least one path between any two nodes. There are no self loops or duplicate edges.

The constraints are important:

  • n <= 500
  • edges.length <= 10^4
  • Edge weights can be as large as 10^6

These constraints are too large for exhaustive path enumeration. The number of possible paths in a graph can grow exponentially, especially in cyclic graphs. We therefore need a shortest path algorithm that efficiently incorporates the additional state introduced by hop usage.

The key complication is that reaching the same node with different numbers of hops remaining represents different states. For example, reaching node 5 with 2 hops left is much better than reaching node 5 with 0 hops left, even if the current distance is identical.

Several edge cases are especially important:

  • The optimal solution may not use all k hops.
  • The cheapest edge is not always the best edge to hop over.
  • A node may need to be revisited with a different hop count.
  • The shortest ordinary path is not necessarily the shortest hopped path.
  • Since weights are positive, Dijkstra's algorithm remains valid after expanding the state space.

Approaches

Brute Force Approach

A brute force solution would enumerate all possible paths from s to d. For every path, we could choose up to k edges whose weights become zero and compute the minimum achievable cost for that path.

This approach is correct because it explores every possible valid solution. However, it is computationally infeasible.

Graphs can contain cycles, and even if we restrict ourselves to simple paths, the number of possible paths between two nodes may be exponential. Additionally, for every path we would also need to consider combinations of edges to hop over.

The complexity becomes prohibitively large and cannot handle graphs with hundreds of nodes and thousands of edges.

Optimal Approach

The important insight is that this is still a shortest path problem, but the state must include more information than just the current node.

Normally, Dijkstra's algorithm stores:

  • Current node
  • Minimum distance to that node

Here, we must also track:

  • How many hops have been used so far

This creates a layered graph conceptually:

  • State (node, hopsUsed)

From each state, we have two transitions for every edge:

  1. Traverse normally:
  • Cost increases by edge weight
  • Hop count unchanged
  1. Use a hop:
  • Cost unchanged
  • Hop count increases by 1

Because all transition costs are non negative, Dijkstra's algorithm still works correctly on this expanded state graph.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Enumerates all paths and hop combinations
Optimal O((n + m) * k * log(nk)) O(nk) Dijkstra on expanded state space

Here, m represents the number of edges.

Algorithm Walkthrough

  1. Build an adjacency list for the graph.

Since the graph is undirected, each edge [u, v, w] is added in both directions. The adjacency list allows efficient neighbor traversal during Dijkstra's algorithm. 2. Create a distance table.

We define:

dist[node][h]

This represents the minimum cost to reach node after using exactly h hops.

The table dimensions are:

n x (k + 1)

Every entry is initialized to infinity except:

dist[s][0] = 0
  1. Initialize a priority queue.

Each heap entry contains:

(currentDistance, currentNode, hopsUsed)

The priority queue always expands the currently cheapest state first. 4. Start Dijkstra's algorithm.

Repeatedly pop the minimum distance state from the heap.

If this state is outdated, meaning its distance is larger than the stored value in dist, skip it. 5. Explore neighboring edges normally.

For an edge (neighbor, weight):

newDistance = currentDistance + weight

If this improves:

dist[neighbor][hopsUsed]

update the table and push the new state into the heap. 6. Explore neighboring edges using a hop.

If we still have remaining hops:

hopsUsed < k

then we may traverse the edge with zero additional cost.

The new state becomes:

dist[neighbor][hopsUsed + 1]

with the same distance. 7. Continue until all reachable states are processed.

Since Dijkstra guarantees optimality for non negative edge weights, the first optimal distance for each state is finalized correctly. 8. Return the minimum value among:

dist[d][0], dist[d][1], ..., dist[d][k]

because we may use anywhere from 0 to k hops.

Why it works

The algorithm treats each (node, hopsUsed) pair as a separate graph state. Dijkstra's algorithm guarantees that when a state is removed from the priority queue, its shortest distance has been finalized because all transitions have non negative cost.

By considering both possible transitions for every edge, normal traversal and hopped traversal, the algorithm explores every valid path configuration. Therefore, the minimum recorded distance to the destination across all allowable hop counts is the true shortest achievable path.

Python Solution

from typing import List
import heapq

class Solution:
    def shortestPathWithHops(
        self,
        n: int,
        edges: List[List[int]],
        s: int,
        d: int,
        k: int
    ) -> int:

        graph = [[] for _ in range(n)]

        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        INF = float("inf")

        dist = [[INF] * (k + 1) for _ in range(n)]
        dist[s][0] = 0

        heap = [(0, s, 0)]

        while heap:
            current_dist, node, hops_used = heapq.heappop(heap)

            if current_dist > dist[node][hops_used]:
                continue

            for neighbor, weight in graph[node]:

                # Traverse normally
                normal_dist = current_dist + weight

                if normal_dist < dist[neighbor][hops_used]:
                    dist[neighbor][hops_used] = normal_dist
                    heapq.heappush(
                        heap,
                        (normal_dist, neighbor, hops_used)
                    )

                # Use a hop
                if hops_used < k:
                    hop_dist = current_dist

                    if hop_dist < dist[neighbor][hops_used + 1]:
                        dist[neighbor][hops_used + 1] = hop_dist
                        heapq.heappush(
                            heap,
                            (hop_dist, neighbor, hops_used + 1)
                        )

        return min(dist[d])

The implementation begins by constructing the adjacency list representation of the graph. Since the graph is undirected, every edge is inserted twice.

The dist table stores the minimum distance for every combination of node and hop usage count. This is the core idea of the expanded state space.

The priority queue implements Dijkstra's greedy selection process. Every heap entry contains the current shortest known state.

For every neighboring edge, the algorithm explores two possibilities. The first pays the edge weight normally. The second uses a hop if one is still available, allowing traversal at zero cost.

Whenever a shorter distance is discovered for a state, the distance table is updated and the new state is pushed into the heap.

Finally, the answer is the minimum value across all destination states because the optimal path may use fewer than k hops.

Go Solution

package main

import (
	"container/heap"
	"math"
)

type State struct {
	dist     int
	node     int
	hopsUsed int
}

type PriorityQueue []State

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].dist < pq[j].dist
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(State))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[:n-1]
	return item
}

func shortestPathWithHops(
	n int,
	edges [][]int,
	s int,
	d int,
	k int,
) int {

	graph := make([][][2]int, n)

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]
		w := edge[2]

		graph[u] = append(graph[u], [2]int{v, w})
		graph[v] = append(graph[v], [2]int{u, w})
	}

	inf := math.MaxInt

	dist := make([][]int, n)

	for i := 0; i < n; i++ {
		dist[i] = make([]int, k+1)

		for j := 0; j <= k; j++ {
			dist[i][j] = inf
		}
	}

	dist[s][0] = 0

	pq := &PriorityQueue{}
	heap.Init(pq)

	heap.Push(pq, State{0, s, 0})

	for pq.Len() > 0 {

		current := heap.Pop(pq).(State)

		currentDist := current.dist
		node := current.node
		hopsUsed := current.hopsUsed

		if currentDist > dist[node][hopsUsed] {
			continue
		}

		for _, edge := range graph[node] {

			neighbor := edge[0]
			weight := edge[1]

			// Traverse normally
			normalDist := currentDist + weight

			if normalDist < dist[neighbor][hopsUsed] {
				dist[neighbor][hopsUsed] = normalDist

				heap.Push(
					pq,
					State{normalDist, neighbor, hopsUsed},
				)
			}

			// Use a hop
			if hopsUsed < k {

				hopDist := currentDist

				if hopDist < dist[neighbor][hopsUsed+1] {

					dist[neighbor][hopsUsed+1] = hopDist

					heap.Push(
						pq,
						State{hopDist, neighbor, hopsUsed + 1},
					)
				}
			}
		}
	}

	answer := inf

	for hops := 0; hops <= k; hops++ {
		if dist[d][hops] < answer {
			answer = dist[d][hops]
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python solution but requires an explicit heap implementation using the container/heap package.

A custom State struct stores the node, distance, and hop count. The adjacency list uses slices of fixed size arrays for compact storage.

Go integers are sufficient because the maximum possible path cost remains within 32 bit integer range, but using standard int is still preferable for compatibility with heap operations and arithmetic.

Worked Examples

Example 1

Input:

n = 4
edges = [[0,1,4],[0,2,2],[2,3,6]]
s = 1
d = 3
k = 2

Graph

1 --4-- 0 --2-- 2 --6-- 3

Initial State

Node Hops Used Distance
1 0 0

Heap:

[(0, 1, 0)]

Step 1

Pop:

(0, 1, 0)

Explore edge (1 -> 0, weight 4).

Normal traversal:

distance = 0 + 4 = 4

Hop traversal:

distance = 0

Updated states:

Node Hops Used Distance
0 0 4
0 1 0

Step 2

Pop:

(0, 0, 1)

Explore (0 -> 2, weight 2).

Normal traversal:

0 + 2 = 2

Hop traversal:

0

Updated:

Node Hops Used Distance
2 1 2
2 2 0

Step 3

Pop:

(0, 2, 2)

Explore (2 -> 3, weight 6).

No hops remain.

Normal traversal:

0 + 6 = 6

Update:

Node Hops Used Distance
3 2 6

Step 4

Later, another path reaches:

3 with cost 2

by hopping over weights 4 and 6.

Final answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O((n + m) * k * log(nk)) Dijkstra over expanded state space
Space O(nk) Distance table plus priority queue

The graph contains n nodes, but the expanded state graph contains n * (k + 1) states because every node may be visited with different hop counts.

Each edge may generate transitions for multiple hop states, producing approximately m * k transitions overall.

Dijkstra's algorithm performs heap operations on these states, leading to the logarithmic factor.

Test Cases

sol = Solution()

# Example 1
assert sol.shortestPathWithHops(
    4,
    [[0,1,4],[0,2,2],[2,3,6]],
    1,
    3,
    2
) == 2  # Use hops on weights 4 and 6

# Example 2
assert sol.shortestPathWithHops(
    7,
    [[3,1,9],[3,2,4],[4,0,9],[0,5,6],[3,6,2],[6,0,4],[1,2,4]],
    4,
    1,
    2
) == 6  # Optimal use of two hops

# Example 3
assert sol.shortestPathWithHops(
    5,
    [[0,4,2],[0,1,3],[0,2,1],[2,1,4],[1,3,4],[3,4,7]],
    2,
    3,
    1
) == 3  # Hop over edge weight 7

# Single edge with one hop
assert sol.shortestPathWithHops(
    2,
    [[0,1,10]],
    0,
    1,
    1
) == 0  # Entire edge can be skipped

# Single edge without hops
assert sol.shortestPathWithHops(
    2,
    [[0,1,10]],
    0,
    1,
    0
) == 10  # Must pay full weight

# Optimal path uses fewer than k hops
assert sol.shortestPathWithHops(
    3,
    [[0,1,1],[1,2,1],[0,2,100]],
    0,
    2,
    2
) == 0  # Hop directly over expensive edge

# Revisiting node with different hop count
assert sol.shortestPathWithHops(
    4,
    [[0,1,5],[1,2,5],[0,2,100],[2,3,1]],
    0,
    3,
    1
) == 6  # Best hop placement matters

# Dense graph
assert sol.shortestPathWithHops(
    4,
    [[0,1,1],[0,2,5],[0,3,10],[1,2,1],[1,3,7],[2,3,1]],
    0,
    3,
    1
) == 0  # Hop over direct edge weight 10

# Larger k than necessary
assert sol.shortestPathWithHops(
    3,
    [[0,1,3],[1,2,4]],
    0,
    2,
    5
) == 0  # All edges can be hopped

Test Summary

Test Why
Example 1 Validates basic multi hop optimization
Example 2 Confirms optimal path selection in larger graph
Example 3 Verifies non obvious hop placement
Single edge with hop Tests full edge elimination
Single edge without hop Tests normal shortest path behavior
Fewer hops used Confirms solution does not require using all hops
Revisiting node Ensures state space expansion is handled correctly
Dense graph Tests multiple competing shortest paths
Large k Ensures excessive hop counts are handled safely

Edge Cases

One important edge case occurs when k = 0. In this situation, the problem reduces to a standard shortest path problem because no edges may be skipped. A buggy implementation might still attempt invalid hop transitions or incorrectly initialize hop states. The solution handles this naturally because the hop transition is only allowed when hopsUsed < k.

Another important case occurs when the optimal path uses fewer than k hops. Some incorrect implementations force exactly k hops to be used, which can produce suboptimal answers. This implementation avoids that issue by returning the minimum value across all destination states from 0 through k.

A third tricky case involves revisiting the same node with different hop counts. In ordinary Dijkstra's algorithm, visiting a node once is usually enough. Here, however, reaching node u with 2 remaining hops is fundamentally different from reaching u with no remaining hops. The implementation correctly models these as separate states using the two dimensional distance table.

Another subtle edge case appears when a very expensive edge should be hopped over even if it is not on the ordinary shortest path. A greedy strategy that always hops over the locally largest edge may fail. The expanded state Dijkstra explores all valid possibilities and therefore guarantees the globally optimal answer.