algorithm - 通过m条边的最短路径
问题描述
你好,聪明的人。
我有以下图表问题。
给定一个具有 n 个顶点的完整有向加权图,找出经过 m - 1 条边(路径中的边可能重复)的最短路径(从任何顶点开始)的长度。至于限制 n <= 200,m <= 1e9。
看看限制,我可以说必须有一些聪明的方法,而不需要某种 dp 和图形遍历,但我就是想不出这样的事情。提前致谢。
Example:
n = 3, m = 5
edges:
1 -> 2 weight = 10,
1 -> 3 weight = 100,
2 -> 1 weight = 10,
2 -> 3 weight = 50,
3 -> 1 weight = 30,
3 -> 2 weight = 70,
answer would be 40 (1 -> 2 -> 1 -> 2 -> 1)
解决方案
一个简单的解决方案是运行 BFS(广度优先搜索)直到第 m个级别,并保持最小的权重总和并返回它。
但是在问题中它说我们可以多次包含顶点,直到它们之间有一条路径,所以现在我们可以执行以下步骤:
- 计算图中存在的所有循环,我们可以重用这些循环来计算可能的最小权重。
例如:
在这个问题中,存在一个1-->2-->1
长度 = 3 重量 = 20 的循环,m = 5 的值,现在我们可以使用此路径两次,但如果 m 为 6,那么我们还剩下 1 个节点要包含。
- 现在我们可以计算长度的最小路径(包括剩余节点)
l
(如果 m=6,则为 1)1
并将其添加到上述权重中。(我们将 1-->2 =10)
- 对图中存在的每个循环重复步骤 1 和 2,并保持最小总和。
下面是描述上述解决方案的 c++ 代码(它可能不是 100% 正确,但你会得到基本的想法)
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Edge{
int src, dest, weight;
};
struct Node{
int start_vertex, end_vertex, weight, edge_count=0;
};
class Graph{
public:
vector<vector<pair<int, int>>> adjList;
int V;
Graph(vector<Edge> edges, int V){
adjList.resize(V+1);
this->V = V;
for(Edge edge:edges){
adjList[edge.src].push_back({edge.dest, edge.weight});
}
}
};
int BFS(Graph &g, int m){
queue<Node> Q;
vector<Node> cycles;
// to store min path from vertex i of length j
vector<vector<int>> dp(g.V+1, vector<int>(g.V+1, INT_MAX));
for(int i=0; i<=g.V; i++)
dp[i][0] = 0;
for(int i=1; i<=g.V; i++){
Q.push({i, i, 0, 1});
}
while(!Q.empty()){
Node top = Q.front();
Q.pop();
if(top.edge_count >= g.V) break;
int v = top.end_vertex;
int start_vertex = top.start_vertex;
int weight = top.weight;
int edge_count = top.edge_count;
for(auto x:g.adjList[v]){
// finding all the cycles
if(x.first == start_vertex){
Node n = {start_vertex, v, weight+x.second, edge_count+1};
cycles.push_back(n);
}else{
Q.push({start_vertex, x.first, weight+x.second, edge_count+1});
}
if(dp[start_vertex][edge_count] > weight+x.second){
dp[start_vertex][edge_count] = weight+x.second;
}
}
}
// finding minimum:
int min_weight = INT_MAX;
if(m<=g.V){
for(int i=1; i<=g.V; i++){
min_weight = min(min_weight, dp[i][m]);
}
}
// checking all the cycles for reusability and maintaining min sum
for(int i=0; i<cycles.size(); i++){
int sum = cycles[i].weight;
int length_left_to_cover = m-cycles[i].edge_count;
sum += length_left_to_cover/(cycles[i].edge_count-1) * cycles[i].weight;
int vertices_left_to_include = 0;
if(m-cycles[i].edge_count>0){
vertices_left_to_include = (m-cycles[i].edge_count)%(cycles[i].edge_count-1);
}
min_weight = min(min_weight, sum+dp[cycles[i].start_vertex][vertices_left_to_include]);
}
return min_weight;
}
// 1 -> 2 weight = 10,
// 1 -> 3 weight = 100,
// 2 -> 1 weight = 10,
// 2 -> 3 weight = 50,
// 3 -> 1 weight = 30,
// 3 -> 2 weight = 70,
int main(){
vector<Edge> edges = {
{1, 2, 10},
{1, 3, 100},
{2, 1, 10},
{2, 3, 50},
{3, 1, 30},
{3, 2, 70}
};
int V = 3;
int m = 5;
Graph g(edges, V);
cout<<"Min weight: "<<BFS(g, m);
}
输出:
Min weight: 40
推荐阅读
- django - Django 的单个基于函数的视图(FBV)处理此代码的 GET 和 POST 请求的周期是什么?
- ios - 根据 Swift 中的给定索引对数组重新排序
- spring-boot - Spring Security 5.2.x 中的 OAuth:存储 userInfo 响应
- python - Django如何在保存到数据库之前连接表单数据
- c++ - 如何从班级打印两个坐标?
- java - Kotlin 序列:过滤器 + 先查找 + 映射
- python - 有没有办法通过 Anaconda 或 Python 3 解释 GLPK 或 lp 文件?
- c# - 用户棱镜库 使用 WPF,DataTrigger 无法在 ItemContainerStyle 中触发。获取 ViewModel 实例的任何建议
- node.js - Schema 关系:传入的参数必须是 12 个字节的单个字符串或 24 个十六进制字符的字符串
- bash - 使用 for 循环时保持格式