Ist Dijkstras Algorithmus für gerichtete oder ungerichtete Graphen?

Question

Ich versuche weiterhin, dies zu googeln, aber die Ergebnisse, die ich finde, fügen nur meiner Verwirrung hinzu. Es scheint, dass es möglicherweise für beide verwendet werden kann? Wenn ja, für welches ist es standardmäßig vorgesehen und was muss geändert werden, damit es nicht-standardmässig funktioniert (egal ob gerichtet oder ungerichtet)?

Edit: als Referenz, ich hatte ein Problem im letzten Semester, wo ich eine Liste wie diese (Flughäfen) gegeben wurde:

AER,KZN,1.8835 
ASF,KZN,1.3005 
ASF,MRV,1.1204 
CEK,KZN,1.9263 
CEK,OVB,1.6733 
DME,KZN,1.7892 
DME,NBC,2.2319 
DME,UUA,2.3786 
EGO,KGD,1.4649 
EGO,KZN,1.2603 
GYD,NBC,2.0755 

Mir wurde gesagt, es gerichtet war, und fragte den kürzesten Weg zu finden. Ich habe es in einen Dijkstra-Algorithmus eingegeben, den ich auf Github gefunden habe (es war ein Open-Computer Midterm, also hatten wir nicht annähernd genug Zeit, um den Algorithmus von Grund auf neu zu schreiben) und mein Professor sagte, dass der kürzeste Weg falsch war und dass es war nicht einmal ein möglicher Weg, weil die Liste gerichtet sein sollte. Ich war mir nicht sicher, ob ich dann den Algorithmus oder die Liste modifizieren sollte, um diese Korrektur vorzunehmen. Es endete damit, dass der zweitkürzeste Pfad, den er zurückgab, tatsächlich der kürzeste Weg war, aber ich frage mich immer noch, was das Problem war.

Answer 1

Es kann auf beide angewendet werden. Hier ist der Grund:

Ein ungerichteten Graph ist im Grunde das gleiche wie ein gerichtet Graph mit bidirektionalen Verbindungen (= zwei Anschlüsse in entgegengesetzte Richtungen) zwischen den verbundenen Knoten.

Sie müssen also nichts tun, damit es für einen ungerichteten Graph funktioniert. Sie müssen nur alle Knoten kennen, die von jedem gegebenen Knoten z. eine Adjazenzliste.

Answer 2

Ein gerichteter Graph bedeutet nur, dass die Kanten, die die Scheitelpunkte verbinden, in einer Richtung verbunden sein können, aber nicht in der anderen. Dies bedeutet, dass ein Vertex benachbart sein kann, dieser andere Vertex jedoch nicht an den ersten Vertex angrenzt.

Im Kontext des Dijkstra-Algorithmus spielt es keine Rolle, ob der Graph gerichtet oder ungerichtet ist. Der Algorithmus von Dijkstra verweist einfach auf die benachbarten Eckpunkte eines Eckpunkts. Es ist diese Adjazenzliste, die Sie ändern müssten, wenn Sie ein Diagramm von gerichtet auf ungerichtet ändern würden.

Answer 3

Djikstras-Algorithmus ist in der Regel für Positive gewichtete Grafiken. Vielleicht verwechseln Sie es mit dem BFS-Algorithmus, der im Wesentlichen Dikstras für ungewichtete Graphen ist. Der Unterschied (zwischen Djikstras und BFS) ist, wenn Sie mit gewichteten Pfaden zu tun haben, müssen wir jetzt die Pfadkosten Anpassungen (Gewichte) & die Entscheidungen, welche Knoten nach der aktuellen zu besuchen.

Answer 4

Sie können den Dijkstra-Algorithmus sowohl in gerichteten als auch ungerichteten Diagrammen verwenden, da Sie einfach Kanten in die PriorityQueue einfügen, wenn Sie eine Kante haben, um von Ihrer Adjazenzliste zu reisen. Beispiel: Wenn einer meiner Knoten eine Kante von A nach B mit der Gewichtung 3 hat, kann er, wenn er von BI aus geleitet wird, die Kante nicht wieder zu A hinzufügen, während er von AI zu B hinzugefügt werden kann.

Wie die anderen Antworten, stellen Sie sicher, dass Sie es nicht mit Gewichten verwechseln. Dijkstras Algorithmus läuft auf positiv gewichteten Graphen, ansonsten wäre die Prioritätswarteschlange nutzlos.

In Ihrem Beispiel würde der Dijkstra-Algorithmus funktionieren, da der Graph sowohl gewichtet (positiv) als auch gerichtete Kanten hat.

Der Fehler wäre gewesen, dass die Kanten doppelt in Form eines ungerichteten Graphen zugewiesen wurden. Sie sollten beim Parsen der Kanten am Anfang in Ihre Objekte vorsichtig sein, um die Kanten in der Adjazenzliste nicht zu duplizieren.