数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究检查通过所有可能路径从任何节点到任何其他节点的成本是否相同
测试从任何节点到任何其他节点通过所有可想而知的路径旅行的成本是否相同，是确定图中连接每对节点的众多路径上的权重总和是否相等的问题。此问题影响各种行业，包括优化技术、数据传输系统和运输网络。
一种方法是 Floyd−Warshall 算法，它可以快速确定任何两个网络节点之间的所有最短路径。此方法不断评估中间节点并更新路由成本，以查看节点对之间是否存在成本相等。另一种选择是 Bellman−Ford 方法，即使节点之间的边权重为负，它也可以找到仅具有一个源节点的网络中的最短路径。通过不断地放松边并识别负权重循环，此方法提供了一种确定通过所有路径从任何节点到任何其他节点的通勤成本是否恒定的方法。
使用的方法
Floyd−Warshall 算法
Bellman−Ford 算法
Floyd−Warshall 算法
此方法通过不断评估中间节点并更新路径成本来找到所有节点对之间的最短路径成本。Floyd−Warshall 方法可以快速准确地计算任何两个指定节点之间的最短路径，这使其适用于密集网络。
算法
初始化一个大小为 n x n 的 2D 矩阵 cost 以记录最短路径成本。
将 cost 对角线设置为 0。
使用图更新 cost 矩阵，其中 cost[u][v] 是从节点 u 到 v 的边成本。为没有直接边的单元格分配 INF（无限大）。
示例
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
#define INF INT_MAX
// Function to find the maximum value in a vector
int maxVal(const vector<int>& vec) {
int max = INT_MIN;
for (int i = 0; i < vec.size(); i++) {
if (vec[i] > max) {
max = vec[i];
}
}
return max;
}
// Function to check whether all values in a vector are the same
bool allSame(const vector<int>& vec) {
for (int i = 1; i < vec.size(); i++) {
if (vec[i] != vec[0]) {
return false;
}
}
return true;
}
// Function to check whether the cost of going from any node to any other node via all possible paths is the same
bool isCostSame(const vector<vector<int>>& graph) {
int n = graph.size();
// Initialize a 2D vector to store the shortest path costs
vector<vector<int>> cost(n, vector<int>(n, INF));
// Initialize the diagonal elements as 0
for (int i = 0; i < n; i++) {
cost[i][i] = 0;
}
// Update the cost matrix with the given graph
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
if (graph[u][v] != INF) {
cost[u][v] = graph[u][v];
}
}
}
// Floyd-Warshall algorithm to find all shortest paths
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (cost[i][k] != INF && cost[k][j] != INF && cost[i][k] + cost[k][j] < cost[i][j]) {
cost[i][j] = cost[i][k] + cost[k][j];
}
}
}
}
// Check whether all paths have the same cost
for (int i = 0; i < n; i++) {
vector<int> pathCosts;
for (int j = 0; j < n; j++) {
pathCosts.push_back(cost[i][j]);
}
if (!allSame(pathCosts)) {
return false;
}
}
return true;
}
int main() {
// Example graph
vector<vector<int>> graph = {
{0, 1, INF, 2},
{1, 0, 4, INF},
{INF, 4, 0, 5},
{2, INF, 5, 0}
};
if (isCostSame(graph)) {
cout << "The cost of going from any node to any other node via all possible paths is the same." << endl;
} else {
cout << "The cost of going from any node to any other node via all possible paths is not the same." << endl;
}
return 0;
}
输出
The cost of going from any node to any other node via all possible paths is not the same.
Bellman−Ford 方法
Bellman−Ford 方法是单源最短路径算法的一个著名示例，它特别有用，因为它可以处理具有负边权重的网络并识别负权重循环。此方法依赖于动态规划技术，通过逐步放松其约束来确定最短路径。在过程开始时，源节点与每个其他节点之间的距离设置为无限大。然后，它迭代地放松所有边以缩短路径，直到找到最佳路径。尽管具有适应性，但由于其时间复杂度，Bellman−Ford 方法可能不如其他算法适用于密集网络。对于具有负边权重的图尤其如此。
算法
创建一个包含 src、dest 和 weight 属性的边结构。
创建一个布尔函数 isCostSame，它接受一个 Edge 对象向量 edges 和节点数 numNodes。
初始化一个大小为 numNodes 的向量 dist，并将所有元素设置为 INF，除了源节点，它为 0。
示例
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
#define INF INT_MAX
// Structure to represent an edge
struct Edge {
int src, dest, weight;
};
// Function to check whether the cost of going from any node to any other node via all possible paths is the same
bool isCostSame(const vector<Edge>& edges, int numNodes) {
vector<int> dist(numNodes, INF);
dist[0] = 0; // Set the distance of the source node to 0
// Relax all edges (V-1) times
for (int i = 0; i < numNodes - 1; i++) {
for (const auto& edge : edges) {
int u = edge.src;
int v = edge.dest;
int weight = edge.weight;
if (dist[u] != INF && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
// Check for negative weight cycles
for (const auto& edge : edges) {
int u = edge.src;
int v = edge.dest;
int weight = edge.weight;
if (dist[u] != INF && dist[u] + weight < dist[v]) {
return false; // Negative weight cycle found
}
}
// Check whether all nodes have the same shortest distance
for (int i = 1; i < numNodes; i++) {
if (dist[i] != dist[0]) {
return false; // Shortest distances are not the same
}
}
return true; // All shortest distances are the same
}
int main() {
// Example graph
vector<Edge> edges = {
{0, 1, 1},
{0, 3, 2},
{1, 2, 4},
{2, 3, 5}
};
int numNodes = 4;
if (isCostSame(edges, numNodes)) {
cout << "The cost of going from any node to any other node via all possible paths is the same." << endl;
} else {
cout << "The cost of going from any node to any other node via all possible paths is not the same." << endl;
}
return 0;
}
输出
The cost of going from any node to any other node via all possible paths is not the same.
结论
总之，确定通过所有可能路径从一个节点移动到另一个节点的成本是否相等是图分析中的一个重要主题。Floyd−Warshall 和 Bellman−Ford 是解决此问题的两种有效方法。Floyd−Warshall 方法可用于查找图中任何两个节点之间的所有最短路径成本。因为它适用于有向图和无向图，所以它是一个通用的选择。相比之下，Bellman−Ford 方法旨在查找单源最短路径，并且能够处理具有负边权重的图以及发现负权重循环。
74 次浏览
