# 旅游省钱大法：加权最短路径

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

787. Cheapest Flights Within K Stops | 🟠 |

Prerequisites

Before reading this article, you should learn:

Graduation season is a time of mixed emotions—joy and nostalgia for the past, uncertainty and anticipation for the future. However, these feelings are transient and will eventually fade with time.

As this wonderful period comes to an end, it's the perfect time for a spontaneous graduation trip to let loose and give your youth a perfect conclusion.

In this article, I'll teach you a dynamic programming algorithm to save money on your graduation trip, preserving more capital for your pursuit of poetry and distant horizons.

Imagine you're starting from your school's city and planning to visit multiple cities before finally arriving at your company for your new job. How should you plan your travel route to minimize airfare costs?

Let's take a look at LeetCode problem #787, "Cheapest Flights Within K Stops":

**787. Cheapest Flights Within K Stops** | 力扣 | LeetCode |

There are `n`

cities connected by some number of flights. You are given an array `flights`

where `flights[i] = [from`

indicates that there is a flight from city _{i}, to_{i}, price_{i}]`from`

to city _{i}`to`

with cost _{i}`price`

._{i}

You are also given three integers `src`

, `dst`

, and `k`

, return **the cheapest price** from `src`

* to *`dst`

* with at most *`k`

* stops. *If there is no such route, return* *`-1`

.

**Example 1:**

Input:n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1Output:700Explanation:The graph is shown above. The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700. Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

**Example 2:**

Input:n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1Output:200Explanation:The graph is shown above. The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

**Example 3:**

Input:n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0Output:500Explanation:The graph is shown above. The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

**Constraints:**

`1 <= n <= 100`

`0 <= flights.length <= (n * (n - 1) / 2)`

`flights[i].length == 3`

`0 <= from`

_{i}, to_{i}< n`from`

_{i}!= to_{i}`1 <= price`

_{i}<= 10^{4}- There will not be any multiple flights between two cities.
`0 <= src, dst, k < n`

`src != dst`

The function signature is as follows:

`int findCheapestPrice(int n, int[][] flights, int src, int dst, int K);`

`int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K);`

`def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:`

`func findCheapestPrice(n int, flights [][]int, src int, dst int, K int) int {}`

`var findCheapestPrice = function(n, flights, src, dst, K) {}`

**Clearly, this problem is about finding the shortest path in a weighted directed graph**.

In simple terms, you are given a weighted directed graph and asked to find the path from `src`

to `dst`

with the minimum weight. Additionally, this path must **not exceed K + 1 edges** (passing through

`K`

nodes is equivalent to passing through `K + 1`

edges).Let's analyze the algorithms related to finding the shortest path.

## BFS Algorithm Approach

In our previous article BFS Algorithm Framework Explained, we mentioned that BFS can be used to find the shortest path.

This is because BFS starts from the initial point and spreads out step by step. Naturally, nodes closer to the starting point are visited first. If the destination is encountered during BFS traversal, the path taken is guaranteed to be the shortest.

However, in BFS Algorithm Framework Explained, we used a regular queue `Queue`

to traverse a multi-tree. For the shortest path in a weighted graph, a regular queue won't suffice; we need a priority queue `PriorityQueue`

.

Why? It's understandable. In the traversal of a multi-tree (or extending to an unweighted graph), it's not that the edges have no weight, but rather that each edge has a weight of 1. The path weight between the start and end points is simply the number of edges between them.

Thus, following the BFS logic of spreading out step by step, nodes visited earlier have fewer edges between them and the start, resulting in a smaller cumulative weight.

In other words, nodes that enter the `Queue`

first are closer to the start and have a smaller path weight.

For weighted graphs, however, the number of edges in a path is not directly correlated with the path's weight. Some paths may have fewer edges, but each edge may have a high weight, making the overall path weight large and unlikely to be the shortest.

For example, consider this scenario given in the problem:

You can move from `0`

to `2`

in one step, but the path weight might not be the smallest.

Therefore, for weighted graphs, we need the "automatic sorting" feature of the priority queue to keep nodes with smaller path weights at the front. This approach, combined with BFS, transforms into the Dijkstra Algorithm.

Having discussed the BFS approach, it's to help you understand the concept. In this article, we will mainly focus on how to use dynamic programming to solve this problem. The implementation code for Dijkstra's algorithm is provided at the end for reference.

## Dynamic Programming Approach

In our previous article Dynamic Programming Core Techniques Explained, we mentioned that many problems involving finding the maximum or minimum value can be solved using dynamic programming.

The weighted shortest path problem, even with an additional `K`

constraint, is still a problem of finding the extremum. Dynamic programming can handle it all.

Let's first ignore the `K`

constraint and focus on the "weighted shortest path" problem. Why is it a dynamic programming problem?

For example, suppose I want to calculate the shortest path from `src`

to `dst`

:

What is the minimum weight? I don't know.

But I can break down the problem:

`s1, s2`

are adjacent nodes leading to `dst`

. I know the weights between them, which are `w1, w2`

.

As long as I know the shortest paths from `src`

to `s1, s2`

, I can determine the shortest path from `src`

to `dst`

!

```
minPath(src, dst) = min(
minPath(src, s1) + w1,
minPath(src, s2) + w2
)
```

This is essentially a recursive relationship, and it's that simple.

**However, don't forget that the problem also imposes a constraint that the shortest path "cannot exceed K + 1 edges."**

So, let's define a `dp`

function like this:

`int dp(int s, int k);`

`int dp(int s, int k);`

`def dp(s: int, k: int) -> int:`

`func dp(s int, k int) int {}`

`var dp = function(s, k) {}`

The function is defined as follows:

**Starting from the source node src, the minimum path weight to reach node s within k steps (one step equals one edge) is dp(s, k)**.

Therefore, the base case for the `dp`

function is straightforward:

```
// Definition: the minimum cost to reach s within k steps starting from src
int dp(int s, int k) {
// From src to src, no steps are needed
if (s == src) {
return 0;
}
// If the number of steps is exhausted, there is no solution
if (k == 0) {
return -1;
}
// ...
}
```

```
// Definition: the minimum cost to reach s within k steps starting from src
int dp(int s, int k) {
// From src to src, no steps are needed
if (s == src) {
return 0;
}
// If the number of steps is exhausted, there is no solution
if (k == 0) {
return -1;
}
// ...
}
```

```
# Definition: the minimum cost to reach s from src within k steps
def dp(s: int, k: int) -> int:
# From src to src, no steps are needed
if s == src:
return 0
# If the number of steps is exhausted, there is no solution
if k == 0:
return -1
# ...
```

```
// Definition: the minimum cost to reach s within k steps starting from src
func dp(s, k int) int {
// From src to src, no steps are needed
if s == src {
return 0
}
// If the number of steps is exhausted, there is no solution
if k == 0 {
return -1
}
// ...
}
```

```
// Definition: The minimum cost to reach s from src within k steps
var dp = function(s, k) {
// From src to src, no steps are needed
if (s === src) {
return 0;
}
// If the number of steps is exhausted, there is no solution
if (k === 0) {
return -1;
}
// ...
}
```

The minimum flight cost the problem seeks can be represented as `dp(dst, K+1)`

:

```
int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
// convert the number of transit stops into the number of edges
K++;
// ...
return dp(dst, K);
}
```

```
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
// convert the number of transit stops into the number of edges
K++;
// ...
return dp(dst, K);
}
```

```
def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
# convert the number of transit stops into the number of edges
K += 1
#...
return dp(dst, K)
```

```
func findCheapestPrice(n int, flights [][]int, src int, dst int, K int) int {
// convert the number of transit stops into the number of edges
K++
// ...
return dp(dst, K)
}
```

```
var findCheapestPrice = function(n, flights, src, dst, K) {
// convert the number of transit stops into the number of edges
K++;
// ...
return dp(dst, K);
};
```

When adding a constraint of `K`

edges, how do we write the state transition equation? It's actually the same as before:

What is the minimum path weight from `src`

to `dst`

within `K`

steps? I don't know.

But I can break down the problem:

`s1, s2`

are the adjacent nodes pointing to `dst`

. If I know the minimum path from `src`

to `s1, s2`

within `K - 1`

steps, then I can reach `dst`

from `src`

within `K`

steps.

This can be expressed as the following relationship:

```
dp(dst, k) = min(
dp(s1, k - 1) + w1,
dp(s2, k - 1) + w2
)
```

This is the new state transition equation. If you can understand this formula, you can already solve this problem.

## Code Implementation

Based on the above approach, how do I know that `s1, s2`

are adjacent nodes pointing to `dst`

, with weights `w1, w2`

between them?

I want to know which nodes point to a given node and also know the weights between them, right?

To put it professionally, we need a data structure to record the "indegree" of each node, which stores all adjacent nodes pointing to the node and the weights of the edges between them.

Let's look at the code. We use a hash table `indegree`

to store the indegree and then implement the `dp`

function:

```
class Solution {
// Hash table to record the indegree of each node, where the key is the node number and the value is the adjacent nodes pointing to this node along with their weights
// to -> [from, price]
HashMap<Integer, List<int[]>> indegree;
int src, dst;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
// Convert the number of transit stations into the number of edges
K++;
this.src = src;
this.dst = dst;
indegree = new HashMap<>();
for (int[] f : flights) {
int from = f[0];
int to = f[1];
int price = f[2];
// Record which node points to this node and the weight between them
indegree.putIfAbsent(to, new LinkedList<>());
indegree.get(to).add(new int[] {from, price});
}
return dp(dst, K);
}
// Definition: the shortest path weight from src to s within k steps
int dp(int s, int k) {
// base case
if (s == src) {
return 0;
}
if (k == 0) {
return -1;
}
// Initialize to the maximum value for easy minimum value extraction later
int res = Integer.MAX_VALUE;
if (indegree.containsKey(s)) {
// When s has indegree nodes, decompose into subproblems
for (int[] v : indegree.get(s)) {
int from = v[0];
int price = v[1];
// The shortest path weight required to reach the adjacent indegree node from src
int subProblem = dp(from, k - 1);
// Skip cases where there is no solution
if (subProblem != -1) {
res = Math.min(res, subProblem + price);
}
}
}
// If it is still the initial value, it means this node is unreachable
return res == Integer.MAX_VALUE ? -1 : res;
}
}
```

```
class Solution {
public:
// Hash table to record the indegree of each point, key is the node number, value is the adjacent nodes pointing to this node and the weight between them
// to -> [from, price]
unordered_map<int, vector<pair<int, int>>> indegree;
int src, dst;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
// Convert the number of transit stations to the number of edges
K++;
this->src = src;
this->dst = dst;
for(const auto& f : flights) {
int from = f[0];
int to = f[1];
int price = f[2];
// Record who points to this node and the weight between them
indegree[to].push_back(make_pair(from, price));
}
return dp(dst, K);
}
// Definition: the shortest path weight from src to s within k steps
int dp(int s, int k) {
// base case
if (s == src) {
return 0;
}
if (k == 0) {
return -1;
}
// Initialize to the maximum value for easy minimum value extraction later
int res = INT_MAX;
if (indegree.count(s)) {
// When s has indegree nodes, decompose into subproblems
for(const auto& v : indegree[s]) {
int from = v.first;
int price = v.second;
// The shortest path weight required to reach the adjacent indegree node from src
int subProblem = dp(from, k - 1);
// Skip unsolvable cases
if (subProblem != -1) {
res = min(res, subProblem + price);
}
}
}
// If it is still the initial value, it means this node is unreachable
return res == INT_MAX ? -1 : res;
}
};
```

```
class Solution:
def __init__(self):
# Hash table to record the indegree of each node, key is the node number, value is the adjacent nodes pointing to this node and the weight between them
# to -> [from, price]
self.indegree = {}
self.src = 0
self.dst = 0
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
# Convert the number of transit stations to the number of edges
K += 1
self.src = src
self.dst = dst
for f in flights:
from_, to, price = f
# Record which node points to this node and the weight between them
if to not in self.indegree:
self.indegree[to] = []
self.indegree[to].append([from_, price])
return self.dp(dst, K)
# Definition: the shortest path weight from src to s within k steps
def dp(self, s: int, k: int) -> int:
# base case
if s == self.src:
return 0
if k == 0:
return -1
# Initialize to the maximum value for easy minimum value extraction later
res = float('inf')
if s in self.indegree:
# When s has indegree nodes, decompose into subproblems
for v in self.indegree[s]:
from_, price = v
# The shortest path weight required to reach the adjacent indegree node from src
subProblem = self.dp(from_, k - 1)
# Skip unsolvable cases
if subProblem != -1:
res = min(res, subProblem + price)
# If it is still the initial value, it means this node is unreachable
return -1 if res == float('inf') else res
```

```
func findCheapestPrice(n int, flights [][]int, src, dst, K int) int {
// Hash table to record the indegree of each node, key is the node number, value is the adjacent nodes pointing to this node and the weight between them
// to -> [from, price]
indegree := make(map[int][][2]int)
// Convert the number of transit stations to the number of edges
K++
for _, f := range flights {
from, to, price := f[0], f[1], f[2]
// Record which node points to this node and the weight between them
indegree[to] = append(indegree[to], [2]int{from, price})
}
return dp(src, dst, K, indegree)
}
// Definition: the minimum cost to reach s within k steps starting from src
func dp(src, s, k int, indegree map[int][][2]int) int {
// base case
if s == src {
return 0
}
if k == 0 {
return -1
}
// Initialize to the maximum value for easy minimum value extraction later
res := math.MaxInt32
if v, ok := indegree[s]; ok {
// When s has indegree nodes, decompose into subproblems
for _, p := range v {
from, price := p[0], p[1]
// The shortest path weight required to reach the adjacent indegree node from src
subProblem := dp(src, from, k - 1, indegree)
// Skip unsolvable cases
if subProblem != -1 {
res = min(res, subProblem + price)
}
}
}
// If it is still the initial value, it means this node is unreachable
if res == math.MaxInt32 {
return -1
}
return res
}
```

```
var findCheapestPrice = function(n, flights, src, dst, K) {
// Hash table to record the indegree of each node, where the key is the node number and the value is the adjacent nodes pointing to this node along with the weights
// to -> [from, price]
let indegree = new Map();
// Convert the number of transit stops into the number of edges
K++;
for (let f of flights) {
let from = f[0];
let to = f[1];
let price = f[2];
// Record which node points to this node and the weight between them
if (!indegree.has(to)) {
indegree.set(to, []);
}
indegree.get(to).push([from, price]);
}
return dp(src, dst, K, indegree);
};
// Definition: the minimum cost to reach s from src within k steps
var dp = function(src, s, k, indegree) {
// base case
if (s === src) {
return 0;
}
if (k === 0) {
return -1;
}
// Initialize to the maximum value for easy minimum value extraction later
let res = Infinity;
if (indegree.has(s)) {
// When s has indegree nodes, decompose into subproblems
for (let v of indegree.get(s)) {
let from = v[0];
let price = v[1];
// The shortest path weight required to reach the adjacent indegree node from src
let subProblem = dp(src, from, k - 1, indegree);
// Skip unsolvable cases
if (subProblem !== -1) {
res = Math.min(res, subProblem + price);
}
}
}
// If it is still the initial value, it means this node is unreachable
return res === Infinity ? -1 : res;
};
```

With the previous foundation, the logic of this solution should be quite clear. Of course, for dynamic programming problems, overlapping subproblems must be eliminated.

Why are there overlapping subproblems? It's simple. If a node points to two other nodes, these two nodes share a common incoming node, leading to repeated recursive calculations.

How to eliminate overlapping subproblems? Identify the "state" of the problem.

What is a state? It's what changes during the problem decomposition (state transition) process.

**What changes? Obviously, it's the parameters s and k of the dp function. With each recursive call, the target point s and the step constraint k change**.

Therefore, this problem has two states, making it a two-dimensional dynamic programming problem. We can use a two-dimensional array `memo`

or a hash table as a memoization tool to reduce redundant calculations.

Let's use a two-dimensional array for memoization. Note that `K`

starts from 1, so the initial size of the memoization array needs to be incremented by one:

```
class Solution {
int src, dst;
HashMap<Integer, List<int[]>> indegree;
// memoization
int[][] memo;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
K++;
this.src = src;
this.dst = dst;
// initialize the memoization table with a special value
memo = new int[n][K + 1];
for (int[] row : memo) {
Arrays.fill(row, -888);
}
indegree = new HashMap<>();
for (int[] f : flights) {
int from = f[0];
int to = f[1];
int price = f[2];
indegree.putIfAbsent(to, new LinkedList<>());
indegree.get(to).add(new int[] {from, price});
}
return dp(dst, K);
}
// definition: the minimum cost to reach s from src within k steps
int dp(int s, int k) {
// base case
if (s == src) {
return 0;
}
if (k == 0) {
return -1;
}
// check the memoization table to prevent redundant calculations
if (memo[s][k] != -888) {
return memo[s][k];
}
// state transition code remains unchanged
int res = Integer.MAX_VALUE;
if (indegree.containsKey(s)) {
for (int[] v : indegree.get(s)) {
int from = v[0];
int price = v[1];
int subProblem = dp(from, k - 1);
if (subProblem != -1) {
res = Math.min(res, subProblem + price);
}
}
}
// store in the memoization table
memo[s][k] = res == Integer.MAX_VALUE ? -1 : res;
return memo[s][k];
}
}
```

```
class Solution {
int src, dst;
unordered_map<int, vector<vector<int>>> indegree;
// memoization
vector<vector<int>> memo;
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
K++;
this->src = src;
this->dst = dst;
// initialize the memoization, fill all with a special value
memo = vector<vector<int>>(n, vector<int>(K + 1, -888));
for(const auto& f : flights) {
int from = f[0];
int to = f[1];
int price = f[2];
indegree[to].push_back({from, price});
}
return dp(dst, K);
}
// definition: the minimum cost to reach s within k steps starting from src
int dp(int s, int k) {
// base case
if (s == src) {
return 0;
}
if (k == 0) {
return -1;
}
// check the memoization to prevent redundant calculations
if (memo[s][k] != -888) {
return memo[s][k];
}
// state transition code remains unchanged
int res = INT_MAX;
if (indegree.count(s)) {
for(const auto& v : indegree[s]) {
int from = v[0];
int price = v[1];
int subProblem = dp(from, k - 1);
if (subProblem != -1) {
res = min(res, subProblem + price);
}
}
}
// store in memoization
memo[s][k] = res == INT_MAX ? -1 : res;
return memo[s][k];
}
};
```

```
class Solution:
def __init__(self):
self.src = 0
self.dst = 0
self.indegree = {}
# memoization
self.memo = []
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
K += 1
self.src = src
self.dst = dst
# initialize the memoization with a special value
self.memo = [[-888] * (K + 1) for _ in range(n)]
for f in flights:
from_, to, price = f
if to not in self.indegree:
self.indegree[to] = []
self.indegree[to].append([from_, price])
return self.dp(dst, K)
# definition: the minimum cost to reach s from src within k steps
def dp(self, s: int, k: int) -> int:
# base case
if s == self.src:
return 0
if k == 0:
return -1
# check the memoization to prevent redundant calculations
if self.memo[s][k] != -888:
return self.memo[s][k]
# the state transition code remains unchanged
res = float('inf')
if s in self.indegree:
for v in self.indegree[s]:
from_, price = v
subProblem = self.dp(from_, k - 1)
if subProblem != -1:
res = min(res, subProblem + price)
# store in the memoization
self.memo[s][k] = -1 if res == float('inf') else res
return self.memo[s][k]
```

```
func findCheapestPrice(n int, flights [][]int, src, dst, K int) int {
indegree := make(map[int][][2]int)
K++
// initialize the memoization table with a special value
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, K + 1)
for j := range memo[i] {
memo[i][j] = -888
}
}
for _, f := range flights {
from, to, price := f[0], f[1], f[2]
indegree[to] = append(indegree[to], [2]int{from, price})
}
return dp(src, dst, K, indegree, memo)
}
// definition: the minimum cost to reach s from src within k steps
func dp(src, s, k int, indegree map[int][][2]int, memo [][]int) int {
// base case
if s == src {
return 0
}
if k == 0 {
return -1
}
// check the memoization table to prevent redundant calculations
if memo[s][k] != -888 {
return memo[s][k]
}
// the state transition code remains unchanged
res := math.MaxInt32
if v, ok := indegree[s]; ok {
for _, p := range v {
from, price := p[0], p[1]
subProblem := dp(src, from, k - 1, indegree, memo)
if subProblem != -1 {
res = min(res, subProblem + price)
}
}
}
// store in the memoization table
if res == math.MaxInt32 {
memo[s][k] = -1
} else {
memo[s][k] = res
}
return memo[s][k]
}
```

```
var findCheapestPrice = function(n, flights, src, dst, K) {
let indegree = new Map();
K++;
// initialize the memoization table, fill all with a special value
let memo = new Array(n).fill(0).map(() => new Array(K + 1).fill(-888));
for (let f of flights) {
let from = f[0];
let to = f[1];
let price = f[2];
if (!indegree.has(to)) {
indegree.set(to, []);
}
indegree.get(to).push([from, price]);
}
return dp(src, dst, K, indegree, memo);
};
// definition: the minimum cost to reach s from src within k steps
var dp = function(src, s, k, indegree, memo) {
// base case
if (s === src) {
return 0;
}
if (k === 0) {
return -1;
}
// check the memoization table to prevent redundant calculations
if (memo[s][k] !== -888) {
return memo[s][k];
}
// state transition code remains unchanged
let res = Infinity;
if (indegree.has(s)) {
for (let v of indegree.get(s)) {
let from = v[0];
let price = v[1];
let subProblem = dp(src, from, k - 1, indegree, memo);
if (subProblem !== -1) {
res = Math.min(res, subProblem + price);
}
}
}
// store in the memoization table
memo[s][k] = res === Infinity ? -1 : res;
return memo[s][k];
};
```

Why is the initial value of the memo set to -888? As mentioned in the previous article How to Determine Base Cases and Initial Values for Memoization, you can initialize it with any meaningless value.

With this, the problem is solved using a top-down recursive approach. Of course, you can derive a bottom-up iterative dynamic programming solution from this approach, but due to space limitations, I won't write it out. Essentially, they are the same.

Actually, if you read all the previous articles on dynamic programming, you'll notice that we've been consistently applying the Core Pattern of Dynamic Programming. It's really not that difficult.

Lastly, to expand on this, some readers might wonder: since this problem is essentially about graph traversal, why don't we need a `visited`

set to record the nodes that have already been visited?

I discussed this question in the Dijkstra Algorithm Template, so you can check that out. Additionally, this problem can also be solved using the Dijkstra algorithm template, and the code is as follows:

```
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
List<int[]>[] graph = new LinkedList[n];
for (int i = 0; i < n; i++) {
graph[i] = new LinkedList<>();
}
for (int[] edge : flights) {
int from = edge[0];
int to = edge[1];
int price = edge[2];
graph[from].add(new int[]{to, price});
}
// start the Dijkstra algorithm
// calculate the shortest path from src to dst with at most k transfers
K++;
return dijkstra(graph, src, K, dst);
}
class State {
// the id of the graph node
int id;
// the cost from src node to the current node
int costFromSrc;
// the number of nodes passed from src to the current node
int nodeNumFromSrc;
State(int id, int costFromSrc, int nodeNumFromSrc) {
this.id = id;
this.costFromSrc = costFromSrc;
this.nodeNumFromSrc = nodeNumFromSrc;
}
}
// input a starting point src, calculate the shortest distance from src to other nodes
int dijkstra(List<int[]>[] graph, int src, int k, int dst) {
// define: the shortest path weight from src to node i is distTo[i]
int[] distTo = new int[graph.length];
// define: the minimum weight path from src to node i must pass through at least nodeNumTo[i] nodes
int[] nodeNumTo = new int[graph.length];
Arrays.fill(distTo, Integer.MAX_VALUE);
Arrays.fill(nodeNumTo, Integer.MAX_VALUE);
// base case
distTo[src] = 0;
nodeNumTo[src] = 0;
// priority queue, where nodes with smaller costFromSrc come first
Queue<State> pq = new PriorityQueue<>((a, b) -> {
return a.costFromSrc - b.costFromSrc;
});
// start BFS from the starting point src
pq.offer(new State(src, 0, 0));
while (!pq.isEmpty()) {
State curState = pq.poll();
int curNodeID = curState.id;
int costFromSrc = curState.costFromSrc;
int curNodeNumFromSrc = curState.nodeNumFromSrc;
if (curNodeID == dst) {
// found the shortest path
return costFromSrc;
}
if (curNodeNumFromSrc == k) {
// the number of transfers is exhausted
continue;
}
// add the neighbors of curNode to the queue
for (int[] neighbor : graph[curNodeID]) {
int nextNodeID = neighbor[0];
int costToNextNode = costFromSrc + neighbor[1];
// consume 1 transfer
int nextNodeNumFromSrc = curNodeNumFromSrc + 1;
// update the dp table
if (distTo[nextNodeID] > costToNextNode) {
distTo[nextNodeID] = costToNextNode;
nodeNumTo[nextNodeID] = nextNodeNumFromSrc;
}
// pruning, if the number of transfers is higher and the cost is also higher, it cannot be the shortest path
if (costToNextNode > distTo[nextNodeID]
&& nextNodeNumFromSrc > nodeNumTo[nextNodeID]) {
continue;
}
pq.offer(new State(nextNodeID, costToNextNode, nextNodeNumFromSrc));
}
}
return -1;
}
}
```

```
class Solution {
public:
struct State {
// ID of the graph node
int id;
// Cost from src node to the current node
int costFromSrc;
// Number of nodes passed from src node to the current node
State(int id, int costFromSrc, int nodeNumFromSrc) {
this->id = id;
this->costFromSrc = costFromSrc;
this->nodeNumFromSrc = nodeNumFromSrc;
}
};
// Custom comparator to prioritize elements with smaller costFromSrc in the priority queue
class CompareState {
public:
bool operator()(State const& s1, State const& s2) {
return s1.costFromSrc > s2.costFromSrc;
}
};
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
vector<vector<int*>> graph(n);
for (vector<int> edge : flights) {
int from = edge[0];
int to = edge[1];
int price = edge[2];
int* arr = new int[2]{to, price};
graph[from].push_back(arr);
}
// Start Dijkstra's algorithm
// Calculate the shortest path from src to dst with at most k transfers
K++;
return dijkstra(graph, src, K, dst);
}
int dijkstra(vector<vector<int*>>& graph, int src, int k, int dst) {
// Definition: The shortest path weight from src to node i is distTo[i]
vector<int> distTo(graph.size(), INT_MAX);
// Definition: The minimum weight path from src to node i must pass through at least nodeNumTo[i] nodes
vector<int> nodeNumTo(graph.size(), INT_MAX);
// base case
distTo[src] = 0;
nodeNumTo[src] = 0;
// Priority queue, elements with smaller costFromSrc are prioritized
priority_queue<State, vector<State>, CompareState> pq;
// Start BFS from the src node
pq.push(State(src, 0, 0));
while (!pq.empty()) {
State curState = pq.top();
pq.pop();
int curNodeID = curState.id;
int costFromSrc = curState.costFromSrc;
int curNodeNumFromSrc = curState.nodeNumFromSrc;
if (curNodeID == dst) {
// Found the shortest path
return costFromSrc;
}
if (curNodeNumFromSrc == k) {
// Transfer count exhausted
continue;
}
// Add adjacent nodes of the current node to the queue
for (int* neighbor : graph[curNodeID]) {
int nextNodeID = neighbor[0];
int costToNextNode = costFromSrc + neighbor[1];
// Transfer count decreases by 1
int nextNodeNumFromSrc = curNodeNumFromSrc + 1;
// Update dp table
if (distTo[nextNodeID] > costToNextNode) {
distTo[nextNodeID] = costToNextNode;
nodeNumTo[nextNodeID] = nextNodeNumFromSrc;
}
// Pruning, if the transfer count is higher and the cost is also higher, it cannot be the shortest path
if (costToNextNode > distTo[nextNodeID]
&& nextNodeNumFromSrc > nodeNumTo[nextNodeID]) {
continue;
}
pq.push(State(nextNodeID, costToNextNode, nextNodeNumFromSrc));
}
}
return -1;
}
};
```

```
from heapq import heappop, heappush
class State:
def __init__(self, id, costFromSrc, nodeNumFromSrc):
self.id = id
self.costFromSrc = costFromSrc
self.nodeNumFromSrc = nodeNumFromSrc
def __lt__(self, other):
return self.costFromSrc < other.costFromSrc
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
graph = [[] for _ in range(n)]
for edge in flights:
from_, to, price = edge
graph[from_].append([to, price])
# start the Dijkstra algorithm
# calculate the shortest path from src to dst with at most k transfers
K += 1
return self.dijkstra(graph, src, K, dst)
# input a source node src, calculate the shortest distance from src to other nodes
def dijkstra(self, graph, src, k, dst):
# definition: the shortest path weight from source src to node i is distTo[i]
distTo = [float('inf')] * len(graph)
# definition: the minimum weight path from source src to node i must pass through at least nodeNumTo[i] nodes
nodeNumTo = [float('inf')] * len(graph)
# base case
distTo[src] = 0
nodeNumTo[src] = 0
# priority queue, nodes with smaller costFromSrc are prioritized
pq = []
heappush(pq, State(src, 0, 0))
while pq:
curState = heappop(pq)
curNodeID = curState.id
costFromSrc = curState.costFromSrc
curNodeNumFromSrc = curState.nodeNumFromSrc
if curNodeID == dst:
# found the shortest path
return costFromSrc
if curNodeNumFromSrc == k:
# transfer count exhausted
continue
# add the neighbors of curNode to the queue
for neighbor in graph[curNodeID]:
nextNodeID, price = neighbor
costToNextNode = costFromSrc + price
# consume 1 transfer count
nextNodeNumFromSrc = curNodeNumFromSrc + 1
# update dp table
if distTo[nextNodeID] > costToNextNode:
distTo[nextNodeID] = costToNextNode
nodeNumTo[nextNodeID] = nextNodeNumFromSrc
# pruning, if the transfer count is higher and the cost is also higher, it will not be the shortest path
if costToNextNode > distTo[nextNodeID] and nextNodeNumFromSrc > nodeNumTo[nextNodeID]:
continue
heappush(pq, State(nextNodeID, costToNextNode, nextNodeNumFromSrc))
return -1
```

```
import (
"container/heap"
"math"
)
func findCheapestPrice(n int, flights [][]int, src int, dst int, K int) int {
graph := make([][]int, n)
for i := 0; i < n; i++ {
graph[i] = []int{}
}
for _, edge := range flights {
from := edge[0]
to := edge[1]
price := edge[2]
graph[from] = append(graph[from], to, price)
}
// start the Dijkstra algorithm
// calculate the shortest path from src to dst with at most k transfers
K++
return dijkstra(graph, src, K, dst)
}
type State struct {
id int
costFromSrc int
nodeNumFromSrc int
}
// input a starting point src, calculate the shortest distance from src to other nodes
func dijkstra(graph [][]int, src int, k int, dst int) int {
// definition: the shortest path weight from src to node i is distTo[i]
distTo := make([]int, len(graph))
// definition: the minimum weight path from src to node i must pass through at least nodeNumTo[i] nodes
nodeNumTo := make([]int, len(graph))
for i := range distTo {
distTo[i] = math.MaxInt
}
for i := range nodeNumTo {
nodeNumTo[i] = math.MaxInt
}
// base case
distTo[src] = 0
nodeNumTo[src] = 0
// priority queue, where states with smaller costFromSrc come first
pq := &PriorityQueue{}
heap.Push(pq, &State{src, 0, 0})
for pq.Len() > 0 {
curState := heap.Pop(pq).(*State)
curNodeID := curState.id
costFromSrc := curState.costFromSrc
curNodeNumFromSrc := curState.nodeNumFromSrc
if curNodeID == dst {
// found the shortest path
return costFromSrc
}
if curNodeNumFromSrc == k {
// transfer limit exhausted
continue
}
// enqueue the adjacent nodes of curNode
for i := 0; i < len(graph[curNodeID]); i += 2 {
nextNodeID := graph[curNodeID][i]
costToNextNode := costFromSrc + graph[curNodeID][i+1]
// consume 1 transfer
nextNodeNumFromSrc := curNodeNumFromSrc + 1
// update dp table
if distTo[nextNodeID] > costToNextNode {
distTo[nextNodeID] = costToNextNode
nodeNumTo[nextNodeID] = nextNodeNumFromSrc
}
// pruning, if the number of transfers is more and the cost is also higher, it will definitely not be the shortest path
if costToNextNode > distTo[nextNodeID] && nextNodeNumFromSrc > nodeNumTo[nextNodeID] {
continue
}
heap.Push(pq, &State{nextNodeID, costToNextNode, nextNodeNumFromSrc})
}
}
return -1
}
type PriorityQueue []*State
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].costFromSrc < pq[j].costFromSrc
}
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[0 : n-1]
return item
}
```

```
var findCheapestPrice = function(n, flights, src, dst, K) {
let graph = new Array(n).fill(0).map(() => []);
for (let edge of flights) {
let from = edge[0];
let to = edge[1];
let price = edge[2];
graph[from].push([to, price]);
}
// start the Dijkstra algorithm
// calculate the shortest path from src to dst with at most k transfers
K++;
return dijkstra(graph, src, K, dst);
};
class State {
constructor(id, costFromSrc, nodeNumFromSrc) {
this.id = id;
this.costFromSrc = costFromSrc;
this.nodeNumFromSrc = nodeNumFromSrc;
}
}
// input a starting point src, calculate the shortest distance from src to other nodes
var dijkstra = function(graph, src, k, dst) {
// define: the shortest path weight from the starting point src to node i is distTo[i]
let distTo = new Array(graph.length).fill(Infinity);
// define: the minimum weight path from the starting point src to node i must pass through at least nodeNumTo[i] nodes
let nodeNumTo = new Array(graph.length).fill(Infinity);
// base case
distTo[src] = 0;
nodeNumTo[src] = 0;
// priority queue, states with smaller costFromSrc come first
let pq = new MinPriorityQueue({ priority: (state) => state.costFromSrc });
pq.enqueue(new State(src, 0, 0));
while (pq.size() > 0) {
let curState = pq.dequeue().element;
let curNodeID = curState.id;
let costFromSrc = curState.costFromSrc;
let curNodeNumFromSrc = curState.nodeNumFromSrc;
if (curNodeID === dst) {
// found the shortest path
return costFromSrc;
}
if (curNodeNumFromSrc === k) {
// transfer count exhausted
continue;
}
// enqueue the neighbors of curNode
for (let neighbor of graph[curNodeID]) {
let nextNodeID = neighbor[0];
let costToNextNode = costFromSrc + neighbor[1];
// consume 1 transfer count
let nextNodeNumFromSrc = curNodeNumFromSrc + 1;
// update dp table
if (distTo[nextNodeID] > costToNextNode) {
distTo[nextNodeID] = costToNextNode;
nodeNumTo[nextNodeID] = nextNodeNumFromSrc;
}
// pruning, if the transfer count is higher and the cost is also higher, it will definitely not be the shortest path
if (costToNextNode > distTo[nextNodeID]
&& nextNodeNumFromSrc > nodeNumTo[nextNodeID]) {
continue;
}
pq.enqueue(new State(nextNodeID, costToNextNode, nextNodeNumFromSrc));
}
}
return -1;
};
```

I won't elaborate on this solution here. You can refer to the previous article Dijkstra Algorithm Template for understanding.