Laluan produk minimum dengan tepi dengan berat lebih besar daripada atau sama dengan 1

Untuk mencari laluan dengan kelebihan terkecil dengan berat lebih besar daripada atau sama dengan 1, kita boleh menggunakan algoritma Dijkstra dengan sedikit pengubahsuaian. Pertama, kami menetapkan berat nod sumber kepada 1 dan berat nod lain kepada infiniti. Semasa pelaksanaan algoritma, kami tidak lagi mengemas kini jarak, tetapi hasil darab pemberat. Ini memastikan laluan dengan berat terkecil dipilih. Dengan memilih nod dengan berat terkecil pada setiap langkah, kami mencari laluan terpendek secara berulang sehingga nod sasaran dicapai. Akhir sekali, hasil darab pemberat di sepanjang laluan ini adalah minimum, memenuhi syarat yang diberikan.

Kaedah penggunaan

• Algoritma Dijkstra yang diubah suai dengan produk berwajaran

• Algoritma Bellman-Ford yang diubah suai dengan produk berwajaran

Algoritma Dijkstra yang dipertingkatkan untuk produk berwajaran

Dalam algoritma Dijkstra yang diubah suai, kami mula-mula menetapkan berat nod sumber kepada infiniti dan pemberat semua nod lain kepada infiniti juga. Semasa melakukan pengiraan, bukannya mengemas kini jarak dengan semua pemberat, kami mengemas kininya dengan hasil darab pemberat yang dihadapi setakat ini. Pada setiap langkah, kami memilih nod dengan berat terkecil dan mengemas kini pemberat nod jirannya dengan cara yang sama. Proses ini berterusan sehingga mencapai nod sasaran. Akhirnya, hasil darab pemberat di sepanjang laluan ini akan mewakili nilai terkecil yang mungkin, memenuhi syarat bahawa berat lebih besar daripada atau sama dengan 1.

Algoritma

• Mulakan semua pemberat tengah kepada infiniti kecuali pusat sumber, yang beratnya ditetapkan kepada 0.

• Buat koleksi pembersihan untuk menjejaki nod yang dipadamkan.

• Apabila terdapat nod yang tidak dilawati,

  • Pilih pusat dengan berat terkecil antara nod yang belum dilawati.

  • Tandai pusat yang dipilih sebagai telah dilawati.

  • Untuk setiap hab bersebelahan yang belum dikunjungi:

• • Kira berat nod pusat semasa dan berat tepi yang disambungkan kepadanya.

  • Jika sebutan yang dikira kurang daripada berat pusat bersebelahan, gantikan beratnya dengan produk yang dikira.

• Ulang langkah 3 sehingga pusat sasaran hilang atau semua pusat dilawati.

• Berat di pusat sasaran mencerminkan berat item terkecil sepanjang perjalanan dari sumber ke titik sasaran.

Contoh

#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: 

Algoritma Bellman-Ford diubah suai dengan produk berwajaran

Dalam algoritma Bellman-Ford yang diselaraskan dengan objek berwajaran, kita mulakan dengan menetapkan pemuatan pusat sumber kepada 1 dan pemuatan semua pusat lain kepada infiniti. Dalam setiap gelung, semua tepi dirungkai dengan membandingkan berat nod semasa dengan beban tepi yang menyambungkannya ke pusat sasaran. Jika berat yang dikira lebih kecil daripada beban pusat sasaran, kami meningkatkan beratnya dengan berat yang dikira. Ulangi proses ini V-1 kali, di mana V ialah jumlah bilangan pusat untuk memastikan semua laluan yang mungkin dipertimbangkan. Berat pusat sasaran mewakili berat terkecil pada laluan dari sumber ke sasaran.

Algoritma

• Kecuali pusat sumber, berat semua pusat lain hendaklah tidak terhingga.

• Ulang langkah di atas V−1 kali, dengan V ialah jumlah bilangan nod:

• • Untuk setiap tepi dalam graf, kira berat item di pusat semasa dan berat tepi yang disambungkan kepadanya.

  • Jika item yang dikira kurang daripada berat pusat sasaran, tingkatkan beratnya dengan produk yang dikira.

• Selepas tempoh V-1, berat semua nod pusat akan ditentukan.

• Semasa pengiraan, jika terdapat kitaran berat negatif dalam graf, kitaran tambahan akan dibezakan. Jika sebarang pemberat diperbetulkan semasa proses ini, ini menunjukkan kewujudan kitaran berat negatif.

• Berat di pusat sasaran mencerminkan berat item terkecil sepanjang perjalanan dari sumber ke titik sasaran.

• Algoritma teduhan tamak memberikan warna kepada bucu secara tamak berdasarkan warna yang tersedia dan warna yang digunakan oleh bucu jiran. Walaupun ia mungkin tidak selalu menggunakan bilangan warna minimum untuk mencapai lorekan graf, ia menyediakan kaedah lorekan bucu yang pantas dan cekap.

Contoh

#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

Kesimpulan

Artikel ini menjelaskan cara mencari laluan dengan kelebihan terkecil dengan berat lebih besar daripada atau sama dengan 1. Ia memperkenalkan dua algoritma, algoritma Dijkstra yang dipertingkatkan dan algoritma Bellman-Ford yang dipertingkatkan, untuk menyelesaikan masalah ini. Algoritma Dijkstra yang diubah suai memilih nod dengan berat minimum pada setiap langkah, manakala algoritma Bellman-Ford yang diubah suai secara berulang membuka lilitan tepi untuk mengemas kini pemberat. Artikel ini menyediakan pelaksanaan kedua-dua algoritma ini dalam bahasa C dan menggambarkan penggunaannya dengan input ujian. Output ialah berat minimum pada laluan dari nod sumber ke nod destinasi.

Atas ialah kandungan terperinci Laluan produk minimum dengan tepi dengan berat lebih besar daripada atau sama dengan 1. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!