資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究權重>=1的邊乘積最小的路徑
為了找到權重大於或等於1的邊乘積最小的路徑，我們可以使用迪克斯特拉演算法並進行一些修改。首先，我們將源節點的權重設定為1，其他所有節點的權重設定為無窮大。在演算法執行過程中，我們不是用權重的和來更新距離，而是用權重的乘積來更新。這確保了選擇權重乘積最小的路徑。透過在每一步中選擇權重乘積最小的節點，我們迭代地找到最短路徑，直到到達目標節點。最後，這條路徑上權重的乘積將是最小的，滿足給定條件。
使用的方法
帶權重乘積的改進迪克斯特拉演算法
帶權重乘積的改進貝爾曼-福特演算法
帶權重乘積的改進迪克斯特拉演算法
在帶權重乘積的改進迪克斯特拉演算法中，我們首先將源節點的權重設定為1，並將所有其他節點的權重設定為無窮大。在演算法執行過程中，我們不是用權重的和來更新距離，而是用迄今為止遇到的權重的乘積來更新它們。在每一步中，我們選擇權重乘積最小的節點，並以相同的方式更新其相鄰節點的權重。這個過程持續進行，直到我們到達目標節點。最後，這條路徑上權重的乘積將表示最小的可能值，滿足權重大於或等於1的條件。
演算法
將所有節點的權重初始化為無窮大，除了源節點，將其設定為0。
建立一個已訪問節點集來跟蹤已訪問的節點。
當存在未訪問節點時，
在未訪問節點中選擇權重乘積最小的節點。
將選定的節點標記為已訪問。
對於每個尚未訪問的相鄰節點
-
計算當前節點的權重和連線它們的邊的權重。
如果計算出的乘積小於相鄰節點的權重，則用計算出的乘積替換其權重。
重複步驟3，直到目標節點被訪問或所有節點都被訪問。
目標節點的權重表示從源節點到目標節點的路徑上權重乘積的最小值。
示例
#include <bits/stdc++.h>
using namespace std;
// Function to return the smallest product of edges
double modifiedDijkstra(int source, int destination, vector<vector<pair<int, double> > > graph)
{
// If the source is equal to the destination
if (source == destination)
return 0;
// Initialize the priority queue
set<pair<double, int>> pq;
pq.insert({1, source});
// Visited array
bool visited[graph.size()] = {0};
// While the priority queue is not empty
while (!pq.empty())
{
// Current node
int current = pq.begin()->second;
// Current product of weights
double product = pq.begin()->first;
// Pop the top-most element
pq.erase(pq.begin());
// If already visited, continue
if (visited[current])
continue;
// Mark the node as visited
visited[current] = true;
// If it is a destination node
if (current == destination)
return product;
// Traverse the neighbors of the current node
for (auto neighbor : graph[current])
{
int neighborNode = neighbor.first;
double weight = neighbor.second;
// Calculate the product of weights
double newProduct = product * weight;
// Insert the new product and neighbor into the priority queue
pq.insert({newProduct, neighborNode});
}
}
// If no path exists
return -1;
}
// Function to add an edge to the graph
void addEdge(vector<vector<pair<int, double>>>& graph, int u, int v, double weight)
{
graph[u].push_back({v, weight});
}
// Function to print the graph
void printGraph(const vector<vector<pair<int, double>>>& graph)
{
for (int i = 1; i < graph.size(); i++)
{
cout << "Node " << i << ": ";
for (auto neighbor : graph[i])
{
cout << "(" << neighbor.first << ", " << neighbor.second << ") ";
}
cout << endl;
}
}
// Driver code
int main()
{
int numNodes = 3;
// Graph as adjacency list
vector<vector<pair<int, double>>> graph(numNodes + 1);
// Input edges
addEdge(graph, 1, 3, 9);
addEdge(graph, 2, 3, 1);
addEdge(graph, 1, 2, 5);
// Source and destination
int source = 1, destination = 3;
// Modified Dijkstra
double smallestProduct = modifiedDijkstra(source, destination, graph);
// Print the result
cout << "Smallest product of weights: " << smallestProduct << endl;
// Print the graph
cout << "Graph: " << endl;
printGraph(graph);
return 0;
}
輸出
Smallest product of weights: 5 Graph: Node 1: (3, 9) (2, 5) Node 2: (3, 1) Node 3:
帶權重乘積的改進貝爾曼-福特演算法
在帶權重乘積的改進貝爾曼-福特演算法中，我們首先將源節點的權重設定為1，並將所有其他節點的權重設定為無窮大。在每個迴圈中，我們透過計算當前節點的權重和連線它們的邊的權重來鬆弛所有邊。如果計算出的乘積小於目標節點的權重，則用計算出的乘積更新其權重。重複此過程V-1次，其中V是節點總數，以確保考慮所有可能的路徑。目標節點的權重表示從源節點到目標節點的路徑上權重乘積的最小值。
演算法
除了源節點，所有其他節點的權重都應為無窮大。
重複以下步驟V-1次，其中V是節點總數
-
對於圖中的每條邊，計算當前節點的權重和連線它們的邊的權重的乘積。
如果計算出的乘積小於目標節點的權重，則用計算出的乘積更新其權重。
經過V-1次迴圈後，所有節點的權重將被最終確定。
在演算法過程中，如果圖中存在負權環，則會識別出一個額外的迴圈。如果在此迭代中更新了任何權重，則表示存在負權環。
目標節點的權重表示從源節點到目標節點的路徑上權重乘積的最小值。
貪婪著色演算法基於可用顏色和相鄰頂點使用的顏色，以貪婪的方式為頂點分配顏色。雖然它可能不會始終給出圖所需的最小顏色數，但它提供了一種快速有效的方法來進行頂點著色。
示例
#include <iostream>
#include <vector>
#include <limits>
struct Edge {
int source, destination;
double weight;
};
// Function to find the smallest product of weights using the modified Bellman-Ford algorithm
double findSmallestProduct(int numNodes, int source, int destination, std::vector<Edge>& edges) {
std::vector<double> weights(numNodes, std::numeric_limits<double>::infinity());
weights[source] = 1;
for (int i = 1; i < numNodes; i++) {
for (const auto& edge : edges) {
double newWeight = weights[edge.source] * edge.weight;
if (newWeight < weights[edge.destination]) {
weights[edge.destination] = newWeight;
}
}
}
for (const auto& edge : edges) {
double newWeight = weights[edge.source] * edge.weight;
if (newWeight < weights[edge.destination]) {
return -1.0; // Negative-weight cycle detected
}
}
return weights[destination];
}
int main() {
int numNodes = 4;
std::vector<Edge> edges = {
{0, 1, 2.0},
{1, 2, 0.5},
{2, 3, 1.5},
{0, 3, 1.2},
{1, 3, 0.8}
};
int source = 0, destination = 3;
double smallestProduct = findSmallestProduct(numNodes, source, destination, edges);
if (smallestProduct < std::numeric_limits<double>::infinity()) {
std::cout << "The smallest product of weights along the path from node " << source
<< " to node " << destination << " is: " << smallestProduct << std::endl;
} else {
std::cout << "A negative-weight cycle is detected. No valid path exists." << std::endl;
}
return 0;
}
輸出
The smallest product of weights along the path from node 0 to node 3 is: 1.2
結論
本文闡明瞭如何找到權重大於或等於1的邊乘積最小的路徑。它介紹了兩種演算法，改進的迪克斯特拉演算法和改進的貝爾曼-福特演算法，用於解決此問題。改進的迪克斯特拉演算法在每一步中選擇權重乘積最小的節點，而改進的貝爾曼-福特演算法迭代地鬆弛邊以更新權重。本文提供了兩種演算法在C語言中的實現，並用測試輸入說明了它們的用法。輸出顯示為從源節點到目標節點的路徑上權重乘積的最小值。
95 次檢視
