Minimaler Produktpfad mit Kanten mit einem Gewicht größer oder gleich 1

Um den Pfad mit der kleinsten Kante mit einem Gewicht größer oder gleich 1 zu finden, können wir den Dijkstra-Algorithmus mit einer leichten Modifikation verwenden. Zuerst setzen wir die Gewichtung des Quellknotens auf 1 und die Gewichtung der anderen Knoten auf unendlich. Während der Ausführung des Algorithmus aktualisieren wir nicht mehr die Distanz, sondern das Produkt der Gewichte. Dadurch wird sichergestellt, dass der Pfad mit dem geringsten Gewicht ausgewählt wird. Indem wir bei jedem Schritt den Knoten mit dem geringsten Gewicht auswählen, ermitteln wir iterativ den kürzesten Weg, bis der Zielknoten erreicht ist. Schließlich wird das Produkt der Gewichte entlang dieses Pfades minimal sein und die gegebene Bedingung erfüllen.

Anwendungsmethode

• Modifizierter Dijkstra-Algorithmus mit gewichtetem Produkt

• Modifizierter Bellman-Ford-Algorithmus mit gewichtetem Produkt

Verbesserter Dijkstra-Algorithmus für gewichtete Produkte

Im modifizierten Dijkstra-Algorithmus setzen wir zunächst die Gewichtung des Quellknotens auf unendlich und die Gewichte aller anderen Knoten ebenfalls auf unendlich. Während wir die Berechnung durchführen, aktualisieren wir die Abstände nicht mit allen Gewichtungen, sondern mit dem Produkt der bisher gefundenen Gewichte. Bei jedem Schritt wählen wir den Knoten mit dem geringsten Gewicht aus und aktualisieren die Gewichte seiner Nachbarknoten auf die gleiche Weise. Dieser Vorgang wird bis zum Erreichen des Zielknotens fortgesetzt. Letztendlich stellt das Produkt der Gewichte entlang dieses Pfads den kleinstmöglichen Wert dar und erfüllt die Bedingung, dass das Gewicht größer oder gleich 1 ist.

Algorithmus

• Alle Mittelgewichte werden auf unendlich initialisiert, mit Ausnahme des Quellzentrums, dessen Gewicht auf 0 gesetzt ist.

• Erstellen Sie eine Bereinigungssammlung, um gelöschte Knoten zu verfolgen.

• Wenn es nicht besuchte Knoten gibt,

  • Wählen Sie unter den nicht besuchten Knoten das Zentrum mit dem geringsten Gewicht aus.

  • Ausgewähltes Zentrum als besucht markieren.

  • Für jeden nicht besuchten angrenzenden Hub:

• • Berechnen Sie das Gewicht des aktuellen Zentralknotens und das Gewicht der damit verbundenen Kanten.

  • Wenn der berechnete Term kleiner ist als das Gewicht des angrenzenden Zentrums, ersetzen Sie dessen Gewicht durch das berechnete Produkt.

• Wiederholen Sie Schritt 3, bis das Zielzentrum verschwindet oder alle Zentren besucht sind.

• Das Gewicht in der Zielmitte spiegelt das kleinste Gegenstandsgewicht auf dem Weg von der Quelle zum Zielpunkt wider.

Beispiel

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

Ausgabe

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

Modifizierter Bellman-Ford-Algorithmus mit gewichtetem Produkt

Im angepassten Bellman-Ford-Algorithmus mit gewichteten Objekten setzen wir zunächst die Belastung des Quellzentrums auf 1 und die Belastung aller anderen Zentren auf unendlich. In jeder Schleife werden alle Kanten entwirrt, indem das Gewicht des aktuellen Knotens mit der Last der Kante verglichen wird, die sie mit dem Zielzentrum verbindet. Ist das berechnete Gewicht kleiner als die Belastung des Zielzentrums, erhöhen wir dessen Gewicht um das berechnete Gewicht. Wiederholen Sie diesen Vorgang V-1 Mal, wobei V die Gesamtzahl der Zentren ist, um sicherzustellen, dass alle möglichen Pfade berücksichtigt werden. Das Gewicht des Zielzentrums stellt das kleinste Gewicht auf dem Weg von der Quelle zum Ziel dar.

Algorithmus

• Mit Ausnahme des Quellzentrums sollte das Gewicht aller anderen Zentren unendlich sein.

• Wiederholen Sie die obigen Schritte V−1 Mal, wobei V die Gesamtzahl der Knoten ist:

• • Berechnen Sie für jede Kante im Diagramm das Gewicht des Gegenstands in der aktuellen Mitte und das Gewicht der damit verbundenen Kanten.

  • Wenn der berechnete Artikel geringer ist als das Gewicht des Zielzentrums, erhöhen Sie sein Gewicht mit dem berechneten Produkt.

• Nach V-1-Perioden werden die Gewichte aller zentralen Knoten bestimmt.

• Wenn während der Berechnung ein negativer Gewichtszyklus in der Grafik vorhanden ist, wird ein zusätzlicher Zyklus unterschieden. Wenn während dieses Vorgangs Gewichte korrigiert werden, deutet dies auf das Vorhandensein eines negativen Gewichtszyklus hin.

• Das Gewicht in der Zielmitte spiegelt das kleinste Gegenstandsgewicht auf dem Weg von der Quelle zum Zielpunkt wider.

• Der Greedy-Shading-Algorithmus weist Scheitelpunkten auf gierige Weise Farben zu, basierend auf den verfügbaren Farben und den von benachbarten Scheitelpunkten verwendeten Farben. Auch wenn für die Diagrammschattierung nicht immer die Mindestanzahl an Farben verwendet wird, bietet es eine schnelle und effiziente Methode zur Scheitelpunktschattierung.

Beispiel

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

Ausgabe

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

Fazit

In diesem Artikel wird erläutert, wie Sie den Pfad mit der kleinsten Kante mit einem Gewicht größer oder gleich 1 finden. Zur Lösung dieses Problems werden zwei Algorithmen vorgestellt, der verbesserte Dijkstra-Algorithmus und der verbesserte Bellman-Ford-Algorithmus. Der modifizierte Dijkstra-Algorithmus wählt bei jedem Schritt den Knoten mit der minimalen Gewichtung aus, während der modifizierte Bellman-Ford-Algorithmus Kanten iterativ entpackt, um Gewichte zu aktualisieren. Der Artikel stellt die Implementierung dieser beiden Algorithmen in C-Sprache bereit und veranschaulicht ihre Verwendung mit Testeingaben. Die Ausgabe ist das Mindestgewicht auf dem Pfad vom Quellknoten zum Zielknoten.

Das obige ist der detaillierte Inhalt vonMinimaler Produktpfad mit Kanten mit einem Gewicht größer oder gleich 1. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!