C++ Dijkstra-Algorithmus - Name/Typ der Druckkante

Question

Ich arbeite gerade an Dijkstra's Kürzestem Pfadproblem. Ich habe nichts Spezifisches in diesem Projekt, Algorithmus ist Standard (implementieren mit Paaren), außer dass ich die Arten von Kanten von einem Scheitelpunkt zum anderen drucken muss.

Stellen Sie sich vor, ich habe 4 Ecken und 5 Kanten. Es gibt ein Paar von Scheitelpunkten p (v1, v2), so dass es zwei oder mehr Kanten gibt, die v1 und v2 verbinden. Zum Beispiel wollen wir die Entfernung von London nach Paris finden. Wir wissen, dass wir beide mit dem Auto fahren können (eine Art von Kante) oder wir können ein Flugticket (eine andere Art von Kante) kaufen. Was ich tun möchte, ist die Art der Kante zu drucken.

Beispiel: Ich habe zwei Möglichkeiten, Paris von London zu erreichen: London -> Calais -> Paris, mindestens 5 Stunden, mit dem Auto; London -> Paris, min. 1 Stunde, mit dem Flugzeug.

Ich weiß genau, wie min-Zeit oder min-Abstand gedruckt wird, wie der Pfad, etc. gedruckt wird. Aber, wie kann ich die Art der Kante (Art des Transports) wie "mit dem Flugzeug" oder "mit dem Auto '? Hier ist, was ich versuchte:

struct neighbor { 

int target_vertex; 
double weight; 
int type; 
// for type: 0 - car 
// 1 - bus 
// 2 - plane 

}; 

Aber dennoch kann ich nicht herausfinden, wie würde ich diese Kante ‚Typen‘ speichern, während kürzesten Weg zu berechnen.

-Code hier: https://gist.github.com/anonymous/5943c448e47ebf0d3964baa53361459d

Answer 1

Das Problem gelöst, alle Szenarios von einer Stadt zur anderen vordefiniert (grundsätzlich - alle Kombinationen der Städte).

if (choice == 1) { 
    switch (from) { 
     case 0: { 
      if (to == 1) std::cout << " by foot "; 
      if (to == 2) std::cout << " by foot -> by bus "; 
      if (to == 3) std::cout << " by air "; 
      break; 
     } 
     case 1: { 
      if (to == 0) std::cout << " by foot "; 
      if (to == 2) std::cout << " by bus "; 
      if (to == 3) std::cout << " by bus -> by car "; 
      break; 
     } 
     case 2: { 
      if (to == 0) std::cout << " by bus -> by foot "; 
      if (to == 1) std::cout << " by bus "; 
      if (to == 3) std::cout << " by car "; 
      break; 
     } 
     case 3: { 
      if (to == 1) std::cout << " by car -> by bus "; 
      if (to == 2) std::cout << " by car "; 
      if (to == 0) std::cout << " by air "; 
     } 
    } 

von = der Startstadt.

to = das Ziel, zu dem wir uns bewegen.

Ich bin sicher, dass die Lösung nicht die beste ist, aber für diesen speziellen Fall mit einer kleinen Anzahl von Knoten und Kanten ist es anwendbar.

Answer 2

Sie haben bereits diese Informationen, es in der prev_type[x] Array gespeichert sind. Dieses Array enthält den Typ transport, den Sie zum Erreichen des letzten Knotens t verwendet haben. Er funktioniert in Kombination mit dem Array prev[], das sich an die übergeordneten Knoten oder den Knotenknoten erinnert, von dem Sie den aktuellen Knoten erreicht haben. Sie beginnen also von Ihrem t (Endknoten) und rufen prev[t], um seinen Eltern zu erhalten, und wird die Art des Transports enthalten, der verwendet wird, um t zu erreichen. Fahren Sie auf diesem Weg zurück bis Sie Ihren s (Start) Knoten erreichen.