Wie kann der Dijkstra-Algorithmus in einem Programm sowohl auf ungerichteten als auch auf gerichteten Algorithmus angewendet werden?

Question

Der Graph wird in dem Format, wie unten dargestellt:

MAX 12 
NODE 1 1 
NODE 2 2 
NODE 3 3 
NODE 4 4 
NODE 5 5 
NODE 6 6 
NODE 7 7 
NODE 9 9 
NODE 8 8 
NODE 10 10 
NODE 11 11 
NODE 12 12 
EDGE 1 2 
EDGE 2 3 
EDGE 3 4 
EDGE 4 5 
EDGE 5 6 
EDGE 6 7 
EDGE 7 8 
EDGE 8 9 
EDGE 9 10 
EDGE 10 11 
EDGE 11 12 
EDGE 1 12 
EDGE 1 3 
EDGE 1 4 
EDGE 1 6 
EDGE 1 8 
EDGE 1 11 
EDGE 1 10 
EDGE 6 10 
EDGE 3 6 
EDGE 4 6 
EDGE 5 7 
EDGE 9 11 

ich die nebenstehenden Liste verwenden müssen in diesen Kanten zu lesen. Aber wenn ich es als ungerichteten Graphen verwenden möchte, das heißt, ignoriere die Direktheit aller Kanten. Wie kann ich die Konnektivität jedes Knotenpaars kennen?

Zum Beispiel kann der kürzeste Abstand zwischen (NODE 2, NODE 8) 2 (2-> 1> 8) in der ungerichteten Graphen, aber die Dijkstra-Algorithmus unter Verwendung von auf dieses Graphen wird 4 (2-> 3-> 6-> 7-> 8). Wie könnte ich den ungerichteten Graphen darstellen, während ich immer noch dieselbe Technik zum Einlesen von Kanten verwende?

Answer 1

Wenn Sie wirklich nicht die Technik des Lesens in den Kanten ändern möchten, müssten Sie über alle anderen Knoten iterieren, um zu sehen, ob sich Ihr Knoten in seiner Adjazenzliste befindet und nicht andersherum.

Dies wird Ihre Laufzeit um einiges erhöhen, während Sie nicht viel Speicher sparen, so würde ich empfehlen, nur die Technik des Lesens in den Rändern zu ändern.