資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究最小反轉邊成本以在每對節點之間存在路徑
為了在每個節點對之間都有一條路徑，反轉邊的最小成本是指找到在圖中改變邊方向的最低成本方法。目標是確保圖中任何兩個節點之間都有一條路徑。這可能涉及改變一些邊的方向以建立連線。最小成本表示與反轉邊相關的最小累積權重。透過最小化成本，我們可以實現具有所有節點對之間路徑的指定結果，同時最佳化調整圖中涉及的總成本。
使用的方法
貪心演算法
帶有邊反轉成本的 Floyd-Warshall 演算法
貪心演算法
為了在每對節點之間建立路徑，切換邊的最小成本可以使用貪心演算法來實現。在這種方法中，我們從一個任意節點開始，並迭代地選擇連線到未訪問節點的邊中成本最低的反轉邊。透過重複此過程，直到所有節點都被訪問，我們確保在每對節點之間建立了一條路徑。該演算法基於在每一步中做出區域性最優選擇的原則，從而導致在最小化總邊反轉成本方面全域性最優的解決方案。
演算法
初始化一個名為“已訪問”的集合以跟蹤已訪問的節點。
選擇一個任意起始節點並將其新增到“已訪問”集合中。
建立一個名為“pq”的優先順序佇列來儲存邊。
對於從起始節點開始的每條有效邊
將邊新增到“pq”，以成本作為優先順序。
初始化一個變數“成本”為 0，表示邊反轉的總成本。
當“已訪問”集合不包含所有節點時
從“pq”中提取成本最低的邊。
如果邊的目標節點不在“已訪問”集合中，
將目標節點新增到“已訪問”集合中。
將邊的成本新增到“成本”變數中。
對於從目標節點開始的每條有效邊
將邊新增到“pq”，以其成本作為優先順序。
輸出最終的“成本”變數，它表示反轉邊的最小成本。
示例
#include <iostream>
#include <vector>
#include <climits>
int getMinCost(const std::vector<std::pair<std::pair<int, int>, int>>& edges, int numVertices) {
std::vector<std::vector<int>> graph(numVertices, std::vector<int>(numVertices, INT_MAX));
for (const auto& edge : edges) {
int u = edge.first.first - 1;
int v = edge.first.second - 1;
int cost = edge.second;
graph[u][v] = cost;
}
for (int k = 0; k < numVertices; k++) {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX) {
graph[i][j] = std::min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
}
int minCost = INT_MAX;
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
if (i != j) {
minCost = std::min(minCost, graph[i][j] + graph[j][i]);
}
}
}
return minCost;
}
int main() {
int numVertices = 5;
std::vector<std::pair<std::pair<int, int>, int>> edges = {
{ { 1, 2 }, 7 },
{ { 5, 1 }, 8 },
{ { 5, 4 }, 5 },
{ { 3, 4 }, 1 },
{ { 3, 2 }, 10 }
};
int minCost = getMinCost(edges, numVertices);
if (minCost == INT_MAX) {
std::cout << "No minimum cost found.\n";
} else {
std::cout << "Minimum cost: " << minCost << '\n';
}
return 0;
}
輸出
Minimum cost: -2147483648
帶有邊反轉成本的 Floyd-Warshall 演算法
帶有邊反轉成本的 Floyd-Warshall 演算法是一種動態規劃演算法，用於在加權圖中找到所有節點對之間的最短路徑。它擴充套件了經典的 Floyd-Warshall 演算法，並考慮了反轉邊的成本。該演算法維護一個表示每個節點對之間最短距離的矩陣。透過迭代地考慮每個節點作為中間頂點，它檢查透過中間節點的路徑是否產生更短的距離。此外，它還考慮反轉邊的成本以找到到達每個節點的最低成本。該演算法確保計算最短路徑，同時考慮邊反轉的成本。
演算法
建立一個大小為 N x N 的距離矩陣 dist，其中所有節點對都初始化為無窮大，其中 N 是圖中的節點數。
對於所有存在的邊，將 dist[i][j] 初始化為節點 i 和 j 之間的邊的權重。
對於每個節點 i
將 dist[i][i] 設定為 0，表示從節點到自身距離為 0。
對於每個節點 k 從 1 到 N
對於每個節點 i 從 1 到 N
對於每個節點 j 從 1 到 N
更新 dist[i][j] 為以下三者的最小值：
dist[i][j]（當前距離）
dist[i][k] + dist[k][j]（透過節點 k 的距離）
dist[j][i] + 反轉從 j 到 k 的邊的成本 + dist[k][i]（透過節點 k 並反轉邊的距離）
輸出最終的 dist 矩陣，其中包含所有節點對之間的最短距離，同時考慮邊反轉的成本。
示例
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
const long long INF = 1e9;
void floydWarshall(vector<vector<long long>>& graph, int numNodes) {
vector<vector<long long>> dist(graph); // Distance matrix initialized with the graph
for (int nodeK = 0; nodeK < numNodes; nodeK++) {
for (int nodeI = 0; nodeI < numNodes; nodeI++) {
for (int nodeJ = 0; nodeJ < numNodes; nodeJ++) {
dist[nodeI][nodeJ] = min(dist[nodeI][nodeJ], dist[nodeI][nodeK] + dist[nodeK][nodeJ] + graph[nodeJ][nodeK]);
}
}
}
// Storing the shortest distances in a string
stringstream result;
result << "Shortest distances between all pairs of nodes:" << endl;
for (int i = 0; i < numNodes; i++) {
for (int j = 0; j < numNodes; j++) {
if (dist[i][j] == INF)
result << "INF ";
else
result << dist[i][j] << " ";
}
result << endl;
}
// Print the result string
cout << result.str();
}
int main() {
int numNodes = 4; // Number of nodes
// Adjacency matrix representation of the graph with edge weights and edge reversal costs
vector<vector<long long>> graph = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floydWarshall(graph, numNodes);
return 0;
}
輸出
Shortest distances between all pairs of nodes: 0 5 INF 10 INF 0 3 INF INF INF 0 1 INF INF INF 0
結論
本文探討了在圖中找到反轉邊的最低成本方法以在每對節點之間建立路徑的問題。它解釋了兩種方法：貪心演算法和帶有邊反轉成本的 Floyd-Warshall 演算法。貪心演算法專注於在每一步中做出區域性最優選擇以最小化總邊反轉成本。另一方面，Floyd-Warshall 演算法考慮所有節點對並動態計算最短路徑，同時考慮反轉邊的成本。這些演算法提供了在最小化圖中邊反轉的總成本的同時建立網路的解決方案。
242 次瀏覽
