数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究图中从源点 S 到目标点 D 且恰好具有 K 条边的最短路径（针对多个查询）
在图中找到从源顶点到目标顶点且恰好有 K 条边的最短路径，是图遍历中最常见的问题之一。目标是找到权重最小且恰好有 K 条边的最短路径。这个问题在许多实际场景中都有体现，包括交通网络、路由协议和资源分配。
动态规划 (DP) 和 Dijkstra 算法只是解决此问题的一些方法。可以使用多种方法找到给定约束条件下的最短路径。Dijkstra 算法考虑每条边的权重来找到最短路径。DP 利用重叠子问题来推导出最优解。
使用的方法
动态规划
Dijkstra 算法
动态规划
在应用动态规划技术时，首先将手头的问题分解成一系列更简单、重叠的子问题。在寻找恰好有 K 条边的最短路径的上下文中，可以使用 DP 快速确定每个顶点、边数和权重的所有可能组合的最短路径。DP 通过避免不必要的计算并将最优解存储在二维数组中来提供最优解。当问题具有最优子结构时，可以使用相同输入再次使用该过程以获得相同的答案。
算法
创建一个所有值都设置为无穷大的 N x (K+1) 二维数组 dp，然后将其提供给函数 shortestPathDP(graph, source, destination, K)。
对于 1 到 K 之间的每个 k，对于 0 到 N−1 之间的每个顶点 v，对于图[v]中的所有邻居，设置 dp[source][0] = 0。
每当 dp[neighbor.vertex][k−1] = 0 时
应将最小值输入到 dp[v][k] 中。
示例
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// Node structure
struct Node {
int vertex;
int weight;
int edges;
Node(int v, int w, int e) : vertex(v), weight(w), edges(e) {}
};
// DP method to find shortest path with exactly K edges
int shortestPathDP(vector<vector<Node>>& graph, int source, int destination, int K) {
int N = graph.size();
vector<vector<int>> dp(N, vector<int>(K + 1, INT_MAX));
dp[source][0] = 0;
for (int k = 1; k <= K; ++k) {
for (int v = 0; v < N; ++v) {
for (const auto& neighbor : graph[v]) {
if (dp[neighbor.vertex][k - 1] != INT_MAX) {
dp[v][k] = min(dp[v][k], dp[neighbor.vertex][k - 1] + neighbor.weight);
}
}
}
}
return dp[destination][K] != INT_MAX ? dp[destination][K] : -1; // No path found
}
int main() {
// Graph with default input
int N = 5; // Number of vertices
vector<vector<Node>> graph(N);
// Adding edges and weights
graph[0].push_back(Node(1, 4, 1));
graph[0].push_back(Node(2, 2, 1));
graph[1].push_back(Node(2, 1, 1));
graph[1].push_back(Node(3, 5, 1));
graph[2].push_back(Node(3, 8, 1));
graph[2].push_back(Node(4, 10, 1));
graph[3].push_back(Node(4, 2, 1));
int Q = 2; // Number of queries
// Queries
vector<pair<int, pair<int, int> >> queries;
queries.push_back(make_pair(0, make_pair(4, 1))); // Source: 0, Destination: 4, K: 1
queries.push_back(make_pair(1, make_pair(3, 2))); // Source: 1, Destination: 3, K: 2
for (int q = 0; q < Q; ++q) {
int source = queries[q].first;
int destination = queries[q].second.first;
int K = queries[q].second.second;
int shortestPathDPResult = shortestPathDP(graph, source, destination, K);
cout << "Shortest path from " << source << " to " << destination << " with exactly " << K << " edges:\n";
cout << "Using DP: " << shortestPathDPResult << endl;
}
return 0;
}
输出
Shortest path from 0 to 4 with exactly 1 edges: Using DP: -1 Shortest path from 1 to 3 with exactly 2 edges: Using DP: -1
Dijkstra 算法
著名的图遍历方法 Dijkstra 算法通过使用加权图来查找网络中每个顶点之间的最短路径。为了在每个阶段选择具有最短暂定距离的顶点，它维护一个优先级队列。对于具有非负边权重的图，此方法是有效的，并且其结果在各种情况下都是可靠的。
算法
构建一个大小为 N x (K+1) 的二维数组 dist，并将其初始内容设置为无穷大。
创建一个新的空优先级队列 (pq)。
将一个对放入 pq 中，其中没有边数、没有源顶点和没有权重。
示例
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// Node structure
struct Node {
int vertex;
int weight;
int edges;
Node(int v, int w, int e) : vertex(v), weight(w), edges(e) {}
};
// Dijkstra's algorithm to find shortest path with exactly K edges
int shortestPathDijkstra(vector<vector<Node>>& graph, int source, int destination, int K) {
int N = graph.size();
vector<vector<int>> dist(N, vector<int>(K + 1, INT_MAX));
dist[source][0] = 0;
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
pq.push(make_pair(0, make_pair(source, 0)));
while (!pq.empty()) {
pair<int, pair<int, int>> curr = pq.top();
pq.pop();
int vertex = curr.second.first;
int weight = curr.first;
int edges = curr.second.second;
if (vertex == destination && edges == K) {
return weight;
}
if (weight > dist[vertex][edges]) {
continue;
}
for (const auto& neighbor : graph[vertex]) {
int newWeight = weight + neighbor.weight;
int newEdges = edges + 1;
if (newEdges <= K && newWeight < dist[neighbor.vertex][newEdges]) {
dist[neighbor.vertex][newEdges] = newWeight;
pq.push(make_pair(newWeight, make_pair(neighbor.vertex, newEdges)));
}
}
}
return -1; // No path found
}
int main() {
// Graph with default input
int N = 5; // Number of vertices
vector<vector<Node>> graph(N);
// Adding edges and weights
graph[0].push_back(Node(1, 4, 1));
graph[0].push_back(Node(2, 2, 1));
graph[1].push_back(Node(2, 1, 1));
graph[1].push_back(Node(3, 5, 1));
graph[2].push_back(Node(3, 8, 1));
graph[2].push_back(Node(4, 10, 1));
graph[3].push_back(Node(4, 2, 1));
int Q = 2; // Number of queries
// Queries
vector<pair<int, pair<int, int>>> queries;
queries.push_back(make_pair(0, make_pair(4, 1))); // Source: 0, Destination: 4, K: 1
queries.push_back(make_pair(1, make_pair(3, 2))); // Source: 1, Destination: 3, K: 2
for (int q = 0; q < Q; ++q) {
int source = queries[q].first;
int destination = queries[q].second.first;
int K = queries[q].second.second;
int shortestPathDijkstraResult = shortestPathDijkstra(graph, source, destination, K);
cout << "Shortest path from " << source << " to " << destination << " with exactly " << K << " edges:\n";
cout << "Using Dijkstra: " << shortestPathDijkstraResult << endl;
}
return 0;
}
输出
Shortest path from 0 to 4 with exactly 1 edges: Using Dijkstra: -1 Shortest path from 1 to 3 with exactly 2 edges: Using Dijkstra: 9
结论
在图论中，在具有恰好 K 条边的网络中找到给定源和指定目标之间的最短路径是一个具有挑战性的问题，并且在许多实际应用中都有应用。动态规划 (DP) 和 Dijkstra 算法只是可以有效解决此问题并找到所需最短路径的一些方法。这些技术使我们能够有效地管理多个查询，在给定约束条件下找到最佳路径，并促进有效的路线规划和优化。这些算法在问题解决方案中提供了适应性，满足了各种图结构和问题规范的需求。总而言之，这些方法是解决图中具有固定 K 条边的最短路径问题的有用资源。
更新于: 2023年7月17日
446 次查看
广告