fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
旅游省钱大法：加权最短路径 :: labuladong的算法小抄
这里的k的判断其实是有问题的吧？k==0只是代表没有了中转的机会，并不是不可达(还可直接从起点到终点)，所以应该将if (k == 0)改为if (k < 0)吧？
另外其实还有另外一种思路，即倒着过来求，将dp定义为dp(int start, int k)，即当前中转次数为k时，从start到dst的最短路径，对应的dp要更改为
// 在中转次数为k的情况下从start到dst的最短路径
public int dp(int start, int k) {
if (start == dst) {
return 0;
}
if (k > this.k) {
return -1;
}
if (memo[start][k] != -666) {
return memo[start][k];
}
int res = Integer.MAX_VALUE;
if (outdegree.containsKey(start)) {
for (int[] element : outdegree.get(start)) {
int to = element[0];
int price = element[1];
int subProblem = dp(to, k + 1);
if (subProblem == -1) continue;
res = Math.min(res, subProblem + price);
}
}
memo[start][k] = res == Integer.MAX_VALUE ? -1 : res;
return memo[start][k];
}
此时也要注意对k的判断
@LovesAsuna 嗯，k == 0 代表没有中转，当起点等于终点的时候确实是一种可行情况，但是：
1、这种边界问题的关键是看题目给的数据边界，题目说了 src != dst。所以你说的没问题，但单就这道题来说，k == 0 直接返回 -1 也是没问题的。
2、我们在一开始给输入的 k 做了 +1 的处理，题目给定的 k 的范围是大于等于 0，那么加一后 k 也不可能等于 0。
@LovesAsuna 我上面说的是 dp 函数递归开始时的情况，我又仔细理解了一下你的问题，你问的应该是递归的过程中，s 被视作起点不断变化，如果当 k == 0 时 s 恰好就是 src，这种情况不应该返回 -1。
是的，这就是我们找到答案的时候，实际上这种情况算法也没有返回 -1，而是返回了 0，因为判断 s == src 的 base case 在前，k == 0 的判断在后。
呜呜呜看了这节的题目没看大佬分析，自己尝试自己分析一下，没想到真的写出来了，写的代码有些粗糙劣质~~现在就去完善，谢谢大佬
class Solution {
int[][] memo;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
memo = new int[n+1][k+2];
return dp(n, flights, src, dst, k+1);
}
public int dp(int n, int[][] flights, int src, int dst, int k){
// base case
if(k < 0){
return -1;
}else if(src == dst){
return 0;
}
if(memo[src][k] != 0){
return memo[src][k];
}
int res = Integer.MAX_VALUE;
for(int[] f : flights){
if(f[0] != src)
continue;
int subProblem = dp(n, flights, f[1], dst, k-1);
if(subProblem == -1){
continue;
}
res = Math.min(res, subProblem + f[2]);
}
memo[src][k] = res==Integer.MAX_VALUE?-1:res;
return memo[src][k];
}
}
这个自底向上的方法 ，比较难想清楚，因为这里的i，j 和之前的dp问题不太一样了，这里的i表示中转次数，比较抽象，且要注意 最后需要对最后一行的结果进行求最小值，不懂的，自己画个二维数组看看。 这个比较抽象，如果看不明白，还是看东哥的解答。东哥的解答很清楚,谢谢
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int[][] dp = new int[k+1][n];// [i][j] 表示 从 开始节点 到 j节点 中转 i次的最少价格
for(int i = 0; i<k+1;i++){
Arrays.fill(dp[i],10000*101+1);//全部初始化成为 无法取到的值
//这里为什么初始化成这个样子 需要看看题目里面的限制
//但是如果初始化成 MAX_VALUE 是有bug的 会数值溢出 具体什么原因 自己想
}
for(int[] flight: flights){
int from = flight[0];
int to = flight[1];
int cost = flight[2];
if(src == from){
dp[0][to] = cost;
//中转0 次 从 开始节点 到 to这个节点的花费
}
}
//中转 i次
for(int i = 1;i<k+1;i++){
for(int[] flight : flights){
int from = flight[0];
int to = flight[1];
int cost = flight[2];
//从开始节点 中转 i 次 到达 to 需要的最少花费
//在两种中做选择
//从开始处 中转i-1次到达 from(to的前一个节点) 然后 再从前一个节点 到达目标节点位置
//dp[i][to] 有多种方式到达 to ，这个里面 有最小值 也可能有最大值 反正直接比较就完事了
dp[i][to] = Math.min(dp[i][to],dp[i-1][from]+cost);
}
}
int result = 10000*101+1;
//在所有可能中 找到到达 dst 位置的 最小的cost 作为结果
for(int i = 0; i<k+1;i++){
result = Math.min(result,dp[i][dst]);
}
return result == 10000*101+1 ? -1: result;
}
}
提供一个较粗糙的C++版本的实现，供参考。
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
//梳理数据结构
vector<vector<int>> graphs(n,vector<int>());
vector<vector<int>> weights(n,vector<int>(n,-1));
for(int i=0;i<flights.size();++i){
graphs[flights[i][1]].emplace_back(flights[i][0]);
weights[flights[i][0]][flights[i][1]]=flights[i][2];
}
//动态规划算法
vector<vector<int>> mem(n,vector<int>(k+1,-1));
int res=dp(src,dst,k,graphs,weights,mem);
return res!=1e9?res:-1;
}
int dp(int from,int to,int k,vector<vector<int>> & graphs,vector<vector<int>>& weights,vector<vector<int>> &mem){
if(from==to) return 0;
if(k<0) return 1e9;
if(mem[to][k]!=-1) return mem[to][k];
int res=1e9;
for(int i=0;i<graphs[to].size();++i){
int candidate=graphs[to][i];
res=std::min(res,dp(from,candidate,k-1,graphs,weights,mem)+weights[candidate][to]);
}
mem[to][k]=res;
return mem[to][k];
}
};
Javascript BFS版本:
var findCheapestPrice = function(n, flights, src, dst, k) {
// 构建邻接表
const map = new Array(n).fill(0).map((_, i) => ({id: i, edges: []}))
flights.forEach(flight => {
const [from, to, price] = flight
map[from].edges.push({to, price})
})
let res = new Array(n).fill(Number.MAX_SAFE_INTEGER)
let depth = 0; // 记录深度中转站
let q = [] // TODO: 换成优先级队列
q.push([src, 0])
// BFS
while(q.length && depth <= k + 1) {
let len = q.length
while (len) {
const [cur, curPrice] = q.shift()
len--
if (curPrice >= res[cur]) continue
res[cur] = curPrice
for(const edge of map[cur].edges) {
q.push([edge.to, edge.price + curPrice])
}
}
depth++
}
return res[dst] === Number.MAX_SAFE_INTEGER ? -1 : res[dst]
};
这个自底向上的方法 ，比较难想清楚，因为这里的i，j 和之前的dp问题不太一样了，这里的i表示中转次数，比较抽象，且要注意 最后需要对最后一行的结果进行求最小值，不懂的，自己画个二维数组看看。 这个比较抽象，如果看不明白，还是看东哥的解答。
东哥的解答很清楚,谢谢class Solution { public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { int[][] dp = new int[k+1][n];// [i][j] 表示 从 开始节点 到 j节点 中转 i次的最少价格 for(int i = 0; i<k+1;i++){ Arrays.fill(dp[i],10000*101+1);//全部初始化成为 无法取到的值 //这里为什么初始化成这个样子 需要看看题目里面的限制 //但是如果初始化成 MAX_VALUE 是有bug的 会数值溢出 具体什么原因 自己想 } for(int[] flight: flights){ int from = flight[0]; int to = flight[1]; int cost = flight[2]; if(src == from){ dp[0][to] = cost; //中转0 次 从 开始节点 到 to这个节点的花费 } } //中转 i次 for(int i = 1;i<k+1;i++){ for(int[] flight : flights){ int from = flight[0]; int to = flight[1]; int cost = flight[2]; //从开始节点 中转 i 次 到达 to 需要的最少花费 //在两种中做选择 //从开始处 中转i-1次到达 from(to的前一个节点) 然后 再从前一个节点 到达目标节点位置 //dp[i][to] 有多种方式到达 to ，这个里面 有最小值 也可能有最大值 反正直接比较就完事了 dp[i][to] = Math.min(dp[i][to],dp[i-1][from]+cost); } } int result = 10000*101+1; //在所有可能中 找到到达 dst 位置的 最小的cost 作为结果 for(int i = 0; i<k+1;i++){ result = Math.min(result,dp[i][dst]); } return result == 10000*101+1 ? -1: result; } }
自己该自己的代码 ， 之前的代码感觉写的不够精简， 重构一下
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
// dp[i][j] 表示 经过 j个中转站到达 i 的最低费用
//k+1+1 的原因是 将最后一个节点也理解成中转节点
int[][] dp = new int[n][k+2];
//初始化 ， 到达所有节点的初始化为 最大值 ， 因为要求最低费用
for(int i = 0 ; i< n ; i++){
Arrays.fill(dp[i],Integer.MAX_VALUE);
}
for(int j = 0; j< k+2 ; j++){
dp[src][j] = 0;//任何src 到src 最小都是 0
}
for(int j = 1; j< k+2 ; j++){
for(int[] flight : flights){
/*
flight[0] form
flight[1] to
flight[2] wight
*/
//这一步防止后面的dp[flight[0]][j-1] + flight[2] 这一步出现 Integer.MAX_VALUE 参加运算 出现 数值溢出现象
//也可以在初始化的时候 初始化成一个较大的数 不一定是Integer.MAX_VALUE
if(dp[flight[0]][j-1] == Integer.MAX_VALUE){
continue;
}
dp[flight[1]][j] = Math.min(dp[flight[1]][j],dp[flight[0]][j-1] + flight[2]);
}
}
return dp[dst][k+1] == Integer.MAX_VALUE ? -1 : dp[dst][k+1];
}
}
贴个C++解法，状态选的是K和起点而非K和终点(结果相同)，用二维数组+pair类型直接构造有向加权图，常规DP
class Solution {
vector<vector<int>> memo;
vector<vector<pair<int, int>>> graph;
public:
void buildGraph(vector<vector<int>>& flights, int n) {
graph.assign(n, vector<pair<int, int>>());
for (auto flight: flights) {
int from = flight[0];
int to = flight[1];
int price = flight[2];
graph[from].emplace_back(to, price);
}
}
// 函数返回从src到dst的最多经过K次中转的最便宜价格
int dp(vector<vector<pair<int, int>>>& graph, int src, int dst, int k) {
if (src == dst) return 0; // base case
if (k == -1) return INT_MAX; // 达到中转上限
if (memo[src][k] != -1) return memo[src][k];
int res = INT_MAX;
for (auto neighbor: graph[src]) {
int node = neighbor.first;
int price = neighbor.second;
int subProb = dp(graph, node, dst, k - 1);
if (subProb == INT_MAX) continue;
res = min(res, subProb + price);
}
return memo[src][k] = res;
}
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
buildGraph(flights, n);
memo.assign(n, vector<int> (k + 1, -1));
int res = dp(graph, src, dst, k);
return res == INT_MAX ? -1 : res;
}
};
python
# 计算每个节点的入度以及对应价格
indegree = {}
for item in flights:
start, to, price = item[0], item[1], item[2]
if to not in indegree:
indegree[to] = []
indegree[to].append([start, price])
k += 1 # k个stop = k+1条边，将中转站个数转化成边的条数
memo = [[-1 for _ in range(k+1)] for __ in range(n)]
# dp定义：从 src 出发，大K 步之内到达 end 的最短路径权重
def dp(end, K):
nonlocal src, indegree, memo
# base case
if end == src:
return 0
if K == 0: # 没有剩余步数了
return -1
if memo[end][K] != -1:
return memo[end][K]
res = float('inf') # 初始化：K步内src到end到最短权重路径
# 只有当end节点有入度时，才是可以到达点路径
if end in indegree:
for sub in indegree[end]:# 分解问题
start, price = sub[0], sub[1]
# 从src到达end前置节点所需的最短路径权重
subProblem = dp(start, K-1)
if subProblem != -1: # 跳过无解问题
res = min(res, subProblem+price)
memo[end][K] = res if res != float('inf') else -1
return memo[end][K]
return dp(dst, k)
