具有權重大於等於1的邊的最小乘積路徑

為了發現具有權重大於或等於1的最小邊的路徑，我們可以使用稍作修改的Dijkstra演算法。首先，我們將來源節點的權重設為1，將其他節點的權重設為無限大。在演算法執行過程中，我們不再更新距離，而是更新權重的乘積。這樣可以確保選擇具有最小權重的路徑。透過在每一步選擇權重最小的節點，我們迭代地發現最短路徑，直到達到目標節點。最後，沿著這條路徑的權重乘積將是最小的，滿足給定的條件。

使用的方法

• 修改後的Dijkstra演算法，帶有加權乘積

• 修改的Bellman-Ford演算法，帶有加權乘積

加權乘積的改進Dijkstra演算法

在修改後的Dijkstra演算法中，我們首先將來源節點的權重設為無窮大，將所有其他節點的權重也設為無限大。在執行計算的過程中，我們不是用所有權重來更新距離，而是用到目前為止遇到的權重的乘積來更新它們。在每一步中，我們選擇具有最小權重的節點，並以相同的方式更新其相鄰節點的權重。這個過程一直持續到達目標節點。最終，沿著這條路徑的權重乘積將表示最小可能值，滿足權重大於或等於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: 

修改後的帶有加權乘積的Bellman-Ford演算法

在帶有加權物件的調整後的Bellman-Ford演算法中，我們透過將來源中心的負載設為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的最小邊的路徑。它介紹了兩個演算法，即改進的Dijkstra演算法和改進的Bellman-Ford演算法，用於解決這個問題。改進的Dijkstra演算法在每一步選擇具有最小權重的節點，而改進的Bellman-Ford演算法迭代地解開邊以更新權重。文章提供了這兩個演算法在C語言中的實現，並用測試輸入說明了它們的使用。輸出結果是從來源節點到目標節點的路徑上的最小權重。

以上是具有權重大於等於1的邊的最小乘積路徑的詳細內容。更多資訊請關注PHP中文網其他相關文章！