Minimum product path with edges with weight greater than or equal to 1

To find the path with the smallest edge with weight greater than or equal to 1, we can use Dijkstra's algorithm with a slight modification. First, we set the weight of the source node to 1 and the weight of other nodes to infinity. During the execution of the algorithm, we no longer update the distance, but the product of the weights. This ensures that the path with the smallest weight is selected. By selecting the node with the smallest weight at each step, we iteratively discover the shortest path until the target node is reached. Finally, the product of weights along this path will be minimal, satisfying the given condition.

usage instructions

• Modified Dijkstra’s algorithm with weighted product

• Modified Bellman-Ford algorithm with weighted product

Improved Dijkstra algorithm for weighted products

In the modified Dijkstra algorithm, we first set the weight of the source node to infinity and the weights of all other nodes to infinity. While performing the calculation, instead of updating the distances with all the weights, we update them with the product of the weights encountered so far. At each step, we select the node with the smallest weight and update the weights of its neighboring nodes in the same way. This process continues until reaching the target node. Ultimately, the product of weights along this path will represent the smallest possible value, satisfying the condition that the weight is greater than or equal to 1.

algorithm

• Initialize all center weights to infinity, except the source center, whose weight is set to 0.

• Create a cleanup collection to track deleted nodes.

• When there are unvisited nodes,

  • Select the center with the smallest weight among unvisited nodes.

  • Mark the selected center as visited.

  • For each unvisited adjacent hub:

• • Calculate the weight of the current central node and the weight of the edges connected to it.

  • If the calculated term is less than the weight of the adjacent center, replace its weight with the calculated product.

• Repeat step 3 until the target center disappears or all centers are visited.

• The target center weight reflects the smallest item weight along the way from the source to the target point.

Example

#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;
}

Output

Smallest product of weights: 5
Graph: 
Node 1: (3, 9) (2, 5) 
Node 2: (3, 1) 
Node 3: 

Modified Bellman-Ford algorithm with weighted product

In the adjusted Bellman-Ford algorithm with weighted objects, we start by setting the loading of the source center to 1 and the loading of all other centers to infinity. In each loop, all edges are unraveled by comparing the weight of the current node with the load of the edge connecting them to the target center. If the calculated weight is smaller than the load of the target center, we increase its weight by the calculated weight. Repeat this process V-1 times, where V is the total number of centers to ensure that all possible paths are considered. The weight of the target center represents the smallest weight on the path from the source to the target.

algorithm

• Except the source center, the weight of all other centers should be infinite.

• Repeat the above steps V−1 times, where V is the total number of nodes:

• • For each edge in the graph, calculate the weight of the item at the current center and the weights of the edges connected to them.

  • If the calculated item is less than the weight at the target center, its weight is upgraded with the calculated product.

• After V-1 periods, the weights of all central nodes will be determined.

• During the calculation, if there is a negative weight cycle in the graph, an additional cycle will be distinguished. If any weights are corrected during this process, this indicates the existence of a negative weight cycle.

• The target center weight reflects the smallest item weight along the way from the source to the target point.

• The greedy shading algorithm assigns colors to vertices in a greedy manner based on the available colors and the colors used by neighbor vertices. While it may not always use the minimum number of colors to accomplish graph shading, it provides a fast and efficient method of vertex shading.

Example

#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;
}

Output

The smallest product of weights along the path from node 0 to node 3 is: 1.2

in conclusion

This article illustrates how to find the path with the smallest edge with weight greater than or equal to 1. It introduces two algorithms, the improved Dijkstra algorithm and the improved Bellman-Ford algorithm, for solving this problem. The modified Dijkstra algorithm selects the node with the minimum weight at each step, while the modified Bellman-Ford algorithm iteratively unwraps edges to update weights. The article provides the implementation of these two algorithms in C language and illustrates their use with test inputs. The output is the minimum weight on the path from the source node to the destination node.

The above is the detailed content of Minimum product path with edges with weight greater than or equal to 1. For more information, please follow other related articles on the PHP Chinese website!