資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
