資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告