資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究D'Esopo-Pape演算法：單源最短路徑
D'Esopo-Pape方法以單個源頂點作為起點，查詢該頂點與有向圖中所有其他頂點之間的最短路徑。對於具有負邊權重的圖，此方法優於傳統的Bellman-Ford方法。在執行過程中，此技術使用優先佇列快速選擇間隔最小的頂點。
透過迭代地鬆弛邊並在識別更短路徑時更新距離，D'Esopo-Pape方法查詢圖中的最短路徑。該方法使用優先佇列選擇具有最小暫定距離的頂點，從而最佳化效率並減少不必要的計算。D'Esopo-Pape演算法的許多用途包括計算機網路、交通規劃和資料中心路由。
使用的方法
D’Esopo-Pape演算法
D’Esopo-Pape演算法
D'Esopo-Pape方法迭代地鬆弛邊並更新距離以查詢圖的最短路徑。該方法使用優先佇列選擇具有最小暫定距離的頂點，從而節省多餘的計算並提高效率。
演算法
從具有numVertices個頂點的有向圖開始。
初始化大小為numVertices的距離陣列distance，並將所有距離設定為無窮大，除了源頂點，其距離為0。
建立一個優先佇列pq，用於按遞增順序儲存頂點及其暫定距離。將零距離源頂點插入pq。
如果pq不為空，則執行以下操作：
找到距離pq最近的頂點u。
對於每個u發出的邊：
v是e的目標頂點。
如果distance[u] + weight小於distance[v]，則將distance[v]更新為distance[u] + weight。在pq中插入或更新頂點v及其修正後的暫定距離。
列印源頂點的最短距離。
示例
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
// Structure to represent a directed edge
struct Edge {
int source, destination, weight;
};
// Function to compute single-source shortest paths using D'Esopo-Pape algorithm
void shortestPaths(const std::vector<Edge>& edges, int numVertices, int source) {
std::vector<int> distance(numVertices, INT_MAX); // Initialize distances to infinity
distance[source] = 0; // Distance from source to itself is 0
// Priority queue to store vertices with their tentative distances
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
pq.push(std::make_pair(distance[source], source));
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
// Traverse all adjacent vertices of u
for (const Edge& edge : edges) {
int v = edge.destination;
int weight = edge.weight;
// Relax the edge if a shorter path is found
if (distance[u] + weight < distance[v]) {
distance[v] = distance[u] + weight;
pq.push(std::make_pair(distance[v], v));
}
}
}
// Print the shortest distances from the source
std::cout << "Shortest distances from source " << source << ":\n";
for (int i = 0; i < numVertices; ++i) {
std::cout << "Vertex " << i << ": " << distance[i] << '\n';
}
}
int main() {
// Example usage
int numVertices = 5;
std::vector<Edge> edges = {
{0, 1, 10},
{0, 2, 5},
{1, 3, 1},
{2, 1, 3},
{2, 3, 9},
{2, 4, 2},
{3, 4, 4},
{4, 3, 6}
};
int source = 0;
shortestPaths(edges, numVertices, source);
return 0;
}
輸出
Shortest distances from source 0: Vertex 0: 0 Vertex 1: 3 Vertex 2: 5 Vertex 3: 1 Vertex 4: 2
結論
最後，D'Esopo-Pape方法解決了有向圖單源最短路徑問題。該方法有效地使用優先佇列和迭代鬆弛邊來計算源頂點與圖中所有頂點之間的最短路徑。Dijkstra和Bellman-Ford開發的最短路徑演算法無法處理負邊權重。這使其適用於許多現實世界的情況，其中邊權重表示成本或懲罰。D'Esopo-Pape演算法優化了效率和準確性，同時最大限度地減少了計算量。交通、計算和金融網路都可以使用它。D'Esopo-Pape演算法幫助我們規劃路線，最佳化網路和分配資源。它透過很好地處理具有負權重的有向圖來解決複雜的最短路徑問題。
191次瀏覽
