Kürzester Pfad eines ungerichteten Graphen mit einer zusätzlichen Gewichtskante

Question

Wir verfügen über einen ungerichteten Graphen, Quellknoten, Zielknoten und das Gewicht einer zusätzlichen Kante, die Sie verwenden können, um zwei Knoten zu verbinden, die nicht früher verbunden waren. Sie müssen das Mindestgewicht des Pfades zwischen der Quelle und dem Ziel finden. Sie können die bereitgestellte Kante nur einmal verwenden. Hier ist ein Beispiel: ein Graph mit 5 Kanten wie folgt 1-> 2 das Gewicht ist 1,2-> 3 das Gewicht ist 2,3-> 4 das Gewicht ist 3,4-> 5 das Gewicht ist 1, 1-> 4 das Gewicht ist 3 und Quellknoten ist Knoten 1, Ziel ist Knoten 4. Wir müssen sagen, dass die minimale Pfadlänge. (das ist 2 in diesem Fall) Wir können hinzufügen, eine zusätzliche Kante von Gewicht 1 (hier von 1 bis 5) Ich würde gerne wissen, wie dies in Java implementiert werden kann.

Answer 1

Wenn ich die Frage richtig verstehe, dann alles, was Sie suchen, ist eine Implementierung von Breite erste Suche in Java, die here gefunden werden könnte. und ich sehe keine Verwendung für das zusätzliche Kantengewicht (da dies nur die Entfernung erhöhen würde), es sei denn, du verwendest die zusätzliche Kante, um einen direkten Weg zwischen 1 und 4 zu erzeugen (dh die Quelle und das Ziel), also die kürzeste Entfernung 1. Aber wiederum müssten Sie in jedem Fall prüfen, ob diese Extrakante weniger Gewicht hat als die Breite aus der ersten Suche. Ohne Verwendung der zusätzlichen Kante ist die kürzeste Entfernung in diesem Fall 3, nicht 2.

Answer 2

Nehmen wir an, Sie haben keine Null- und Negativkanten. Sie behalten Kanten in der Anordnung a [N] [N] bei. Ändern eines Graphen Bit:

• make gerichteten Graphen A aus Quelle Graph:

  for (int i = 0; i < N; i++) 
      for (int j = 0; j < N; j++) 
       if (a[i][j] > 0 && a[j][i] == 0) 
        a[j][i] = a[i][j]; 
  

• eine Kopie Graphen machen und wilden Randkante (Wild hinzufügen, gerichtet ist, führt von Teil A Teil B wird vordefiniert Gewicht)

• Array b definieren: int b [2 * N] [2 * N], initialisieren Kanten mit Nullen

  for (int i = 0; i < N; i++) 
      for (int j = 0; j < N; j++) 
       if (a[i][j] == 0) { 
        b[i][N+j] = wildWeight; 
       } else { 
        b[i][j] = a[i][j]; 
        b[N+i][N+j] = a[i][j]; 
       } 
  

Google für Dijkstra-Algorithmus-Implementierung in Java und verwenden Sie es auf dieser Midified-Grafik.