Dijkstras Algorithmus in C ++

Die offensichtlichste Diskrepanz ist, dass Ihr Code nichts mit dem Parent -Array des Pseudocodes zu tun hat. Ich nehme das als Ausgabeparameter, obwohl es nicht explizit so markiert ist. Wie Sie anscheinend erkannt haben, ist es nicht erforderlich, nur die Längen der minimalen Pfade zu berechnen, aber es enthält alle Informationen über die tatsächlichen Schritte in diesen Pfaden, und dies ist oft die gewünschte Information.

Sie haben auch kein Analog zum Pseudocode Nearest ; Es wäre jedoch ein bisschen gemein, sich darüber zu beschweren, denn Nearest ist kein Parameter für die Routine, und der Pseudocode zeigt nicht, dass seine Elemente jemals gelesen werden. Als solches scheint es keinen nützlichen Zweck zu erfüllen.

Es scheint, dass dieser Code auch nicht ganz übereinstimmt:

Die Bedingung && dist[u] != INT_MAX entspricht keinem Pseudocode. (Es ist auch unnötig, da u von minDistance() zurückgegeben wurde und daher diese Bedingung immer erfüllt sein sollte).

Möglicherweise ist Ihr Kursleiter auch unzufrieden damit, dass Sie die minimalen Pfadlängen drucken, anstatt sie zurückzugeben. Es hängt ein wenig vom Pseudocode-Dialekt ab, aber ich würde geneigt sein, das Aussehen von Dist in der Parameterliste als Hinweis darauf zu nehmen, dass es sich um einen Ausgabeparameter und nicht nur um eine interne Variable handelt.

Wenn dein Instruktor extrem wählerisch ist, dann kannst du vielleicht etwas Durchhang bekommen, indem du auf einige scheinbare Fehler im Pseudocode aufmerksam machst:

• Wie bereits erwähnt, ist Nearest kein Parameter, in den geschrieben, aber nie gelesen wird.
• Die Bedingung if Dist[u] ← w(uv) < Dist[v] then sollte stattdessen if Dist[u] + w(uv) < Dist[v] then sein. (Sie haben die korrekte Version implementiert, die als weiterer Unterschied zum Pseudocode interpretiert werden könnte.)
• Es sieht so aus, als ob Parent[r] ← u Parent[v] ← u sein sollte.

Natürlich könnte es sein, dass dein Lehrer wollte, dass du den Pseudocode genau implementierst, Fehler und alles ....

Als eine Strategie hätte ich versucht, Variablennamen zu verwenden, die besser zum Pseudocode passen. Ich denke nicht, dass es fair wäre, wenn der Dozent den Code aus diesen Gründen ablehnt, aber der Vergleich des C ++ Codes mit dem Pseudocode wäre einfacher für alle gewesen, wenn du ein bisschen näher dran gewesen wärst Namen.

Während ich über Ihren Code rede, bemerke ich übrigens, dass, obwohl Ihre minDistance() -Funktion scheinbar die Anforderungen des Pseudocodes implementiert, dies auf ineffiziente Weise geschieht (und Dijkstra ist nicht besonders effizient, um damit zu beginnen ). Der übliche Ansatz verwendet einen Min-Heap, um Knoten zu verfolgen, die gesehen wurden, aber noch nicht besucht wurden, was die Kosten für die Auswahl des Min-Distanz-Knotens von O (n) zu O (log n) reduziert. Nicht, dass es für so wenige Elemente wichtig ist, wie Sie testen, aber für große Graphen ist der Unterschied enorm.

Ein Problem ist, dass ich glaube, dass Ihre MinDistance-Funktion, es scheint, dass Sie nur nicht besuchte Knoten (Zeile 10 if (sptSet [v] == falsch & amp; & dist; [&]; = min)) aktualisieren. Ich denke, das ist falsch. Betrachten Sie das folgende Diagramm (Knoten V = {n1, n2, n3, n4} mit den folgenden Abständen d (n1, n2) = 10; d (n1, n3) = 3; d (n3, n2) = 3 (alle anderen sind unendlich).

Beginnend in n1 entdecken Sie n2 mit den Kosten von 10

Sie entdecken auch n3 mit den Kosten von 3

von n2 entdecken Sie nicht den kürzeren Pfad zu n2 (n1-n3-n2), weil Sie n2 bereits als besucht markiert haben.

Ich bin mir nicht sicher, ob ich wright bin. Wenn nicht mich nicht beschuldigen.