Code Ausgabe auf Graph und einige Ansprüche auf lokalen Wettbewerb?
Ich stieß auf eine Frage wie folgt:
Wir haben einen Code für den gewichteten, azyklischen Graph G(V, E) mit positiven und negativen Kanten. Wir ändern das Gewicht dieses Graphen mit folgendem Code, um eine G ohne negative Kante (G') zu erhalten. Wenn V={1,2...,n} und G_ij ein Gewicht von Kante i zu Kante j sind.
Wir haben zwei Axiome:
1) Der kürzeste Weg zwischen je zwei Ecken in G ist der gleiche wie G '.
2) die Länge des kürzesten Weges zwischen jeweils zwei Ecken in G ist gleich wie G '.
Wir wollen diese beiden Sätze verifizieren. welcher ist wahr und welcher ist falsch. Wer kann einen Hinweis hinzufügen, warum diese wahr oder falsch sind?
Meine Lösung:
Ich denke, zwei ist falsch als folgendes Gegenbeispiel, der ursprüngliche Graph ist links angegeben, und nachdem der Algorithmus ausgeführt wurde, ist das Ergebnis in rechts der kürzeste Pfad zwischen 1 und 3 geändert, er ging von Knoten 2, aber nach dem Algorithmus wird ausgeführt es ging nie von Vertex 2.
1 Antwort
Annahmen:
Es gibt ein paar Probleme mit Ihrer Präsentation der Frage; Ich habe einige Annahmen gemacht, die ich hier klarstellen möchte. Die Antwort auf Ihre Frage im Hinblick auf die Richtigkeit dieser Annahmen finden Sie im folgenden Abschnitt.
Zuerst , wie @amit sagte, Ihre Verwendung von j ist nicht klar. Es scheint, dass du das meintest:
Das heißt, wenn die kleinste Ausgangskante i für jeden Knoten c_i negativ ist, dann erhöhen Sie die Gewichte aller ausgehenden Kanten um -c_i und verringern Sie die Gewichtungen aller eingehenden Kanten um -c_i . Dann wird die kleinste ausgehende Kante ein Gewicht von 0 haben.
Zweite , allein, Dieser Algorithmus garantiert nicht, dass G' keine negativen Kanten hat! Betrachten Sie die folgende Grafik:
Hier wird der Wert der Kante (1,2) durch die Operation 1 auf 0 hochgesetzt, aber durch die Operation 2 auf -1 zurückgesetzt. Sie müssen angeben, dass der Graph in umgekehrter topologischer Reihenfolge ist, sodass die Kante (i,j) immer von j bearbeitet wird, bevor sie von i bearbeitet wird. (Alternativ könnten Sie es in topologischer Reihenfolge sortieren und von n to 1 iterieren.)
Beantworten Sie Ihre Frage:
1) Der kürzeste Weg zwischen zwei Knoten in G ist der gleiche wie in G' .
Das ist wahr. Betrachten Sie einen Pfad nicht als Tupel von Kanten, sondern als Tupel von Knoten. Für die Vertices s und t ist ein Pfad ein Tupel der Knoten (s, v_1, v_2, ..., t) , wobei zwischen jeweils zwei aufeinanderfolgenden Elementen eine Kante vorhanden ist. Für jeden Knoten u , u wurden die Kosten der eingehenden Kanten mit der gleichen Rate gesenkt, mit der die Kosten der ausgehenden Kanten erhöht wurden. Daher sind die relativen Kosten für die Einbeziehung von u in den Pfad unverändert.
2) Die Gewichtung des kürzesten Weges zwischen jeweils zwei Scheitelpunkten in G ist gleich wie in G' .
Das ist falsch. Die Quelle s erhöht ihr Ausgangsgewicht um -c_s , während das Ziel t das Eingangsgewicht um -c_t verringert. Wenn c_s != c_t , dann ist das Gewicht des Pfades nicht gleich.
Um es noch einmal zu wiederholen, das Gewicht jedes Pfades von s bis t wird um (c_t-c_s) erhöht. Daher ist der kürzeste Pfad für ein gegebenes s und t -Paar immer noch der kürzeste Pfad (da alle Pfade zwischen diesem Paar sich um den gleichen Betrag ändern). Allerdings wird das Gewicht nicht unbedingt gleich sein.
Tags und Links algorithm c++ graph-theory data-structures graph