Chemin de produit minimum avec des arêtes de poids supérieur ou égal à 1

Pour trouver le chemin avec la plus petite arête avec un poids supérieur ou égal à 1, on peut utiliser l'algorithme de Dijkstra avec une légère modification. Tout d’abord, nous fixons le poids du nœud source à 1 et le poids des autres nœuds à l’infini. Lors de l'exécution de l'algorithme, on ne met plus à jour la distance, mais le produit des poids. Cela garantit que le chemin ayant le poids le plus faible est sélectionné. En sélectionnant le nœud avec le plus petit poids à chaque étape, nous découvrons itérativement le chemin le plus court jusqu'à ce que le nœud cible soit atteint. Enfin, le produit des poids le long de ce chemin sera minimal, satisfaisant la condition donnée.

Méthode à utiliser

• Algorithme de Dijkstra modifié avec produit pondéré

• Algorithme Bellman-Ford modifié avec produit pondéré

Amélioration de l'algorithme de Dijkstra pour les produits pondérés

Dans l'algorithme de Dijkstra modifié, nous définissons d'abord le poids du nœud source à l'infini et les poids de tous les autres nœuds également à l'infini. Lors du calcul, au lieu de mettre à jour les distances avec tous les poids, nous les mettons à jour avec le produit des poids rencontrés jusqu'à présent. A chaque étape, nous sélectionnons le nœud avec le plus petit poids et mettons à jour les poids de ses nœuds voisins de la même manière. Ce processus se poursuit jusqu'à atteindre le nœud cible. En fin de compte, le produit des poids le long de ce chemin représentera la plus petite valeur possible, satisfaisant la condition selon laquelle le poids est supérieur ou égal à 1.

Algorithme

• Initialisez tous les poids centraux à l'infini, sauf le centre source, dont le poids est fixé à 0.

• Créez une collection de nettoyage pour suivre les nœuds supprimés.

• Quand il y a des nœuds non visités,

  • Sélectionnez le centre avec le plus petit poids parmi les nœuds non visités.

  • Marquer le centre sélectionné comme visité.

  • Pour chaque hub adjacent non visité :

• • Calculez le poids du nœud central actuel et le poids des bords qui y sont connectés.

  • Si le terme calculé est inférieur au poids du centre adjacent, remplacez son poids par le produit calculé.

• Répétez l'étape 3 jusqu'à ce que le centre cible disparaisse ou que tous les centres soient visités.

• Le poids au centre cible reflète le poids du plus petit article tout au long du trajet depuis la source jusqu'au point cible.

Exemple

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

Sortie

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

Algorithme Bellman-Ford modifié avec produit pondéré

Dans l'algorithme Bellman-Ford ajusté avec des objets pondérés, nous commençons par définir le chargement du centre source à 1 et le chargement de tous les autres centres à l'infini. Dans chaque boucle, toutes les arêtes sont démêlées en comparant le poids du nœud actuel avec la charge de l'arête les reliant au centre cible. Si le poids calculé est inférieur à la charge du centre cible, on augmente son poids du poids calculé. Répétez ce processus V-1 fois, où V est le nombre total de centres pour vous assurer que tous les chemins possibles sont pris en compte. Le poids du centre cible représente le plus petit poids sur le chemin allant de la source à la cible.

Algorithme

• À l'exception du centre source, le poids de tous les autres centres devrait être infini.

• Répétez les étapes ci-dessus V−1 fois, où V est le nombre total de nœuds :

• • Pour chaque arête du graphique, calculez le poids de l'élément au centre actuel et le poids des arêtes qui y sont connectées.

  • Si l'article calculé est inférieur au poids du centre cible, améliorez son poids avec le produit calculé.

• Après les périodes V-1, les poids de tous les nœuds centraux seront déterminés.

• Lors du calcul, s'il y a un cycle de poids négatif dans le graphique, un cycle supplémentaire sera distingué. Si des poids sont corrigés au cours de ce processus, cela indique l’existence d’un cycle de poids négatif.

• Le poids au centre cible reflète le poids du plus petit article tout au long du trajet depuis la source jusqu'au point cible.

• L'algorithme d'ombrage glouton attribue des couleurs aux sommets de manière gourmande en fonction des couleurs disponibles et des couleurs utilisées par les sommets voisins. Bien qu'il n'utilise pas toujours le nombre minimum de couleurs pour réaliser l'ombrage de graphique, il constitue une méthode rapide et efficace d'ombrage de sommet.

Exemple

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

Sortie

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

Conclusion

Cet article explique comment trouver le chemin avec le plus petit bord avec un poids supérieur ou égal à 1. Il introduit deux algorithmes, l'algorithme amélioré de Dijkstra et l'algorithme amélioré de Bellman-Ford, pour résoudre ce problème. L'algorithme de Dijkstra modifié sélectionne le nœud avec le poids minimum à chaque étape, tandis que l'algorithme de Bellman-Ford modifié déroule de manière itérative les arêtes pour mettre à jour les poids. L'article présente l'implémentation de ces deux algorithmes en langage C et illustre leur utilisation avec des entrées de test. Le résultat est le poids minimum sur le chemin allant du nœud source au nœud de destination.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!