数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
