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
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;
}
Nach dem Login kopieren
Ausgabe
Smallest product of weights: 5
Graph:
Node 1: (3, 9) (2, 5)
Node 2: (3, 1)
Node 3:
Nach dem Login kopieren
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;
}
Nach dem Login kopieren
Ausgabe
The smallest product of weights along the path from node 0 to node 3 is: 1.2
Nach dem Login kopieren
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!
