Implementation (Part 2)
Lektion 6 von 9 im Kurs Dijkstra-Algorithmus - Graph-Algorithmen von Coddy.
Nun die gierige Kürzeste-Wege-Berechnung.
Aufgabe
MittelErstellen Sie nun den vollständigen Algorithmus.
Schreiben Sie eine Funktion namens dijkstra, die n, das flache edges Array (Tripel, gerichtet, nicht-negative Gewichte) und eine source entgegennimmt und ein Array zurückgibt, in dem die Position v die kürzeste Entfernung von source zu v ist. Verwenden Sie -1 für Knoten, die nicht erreicht werden können.
Beginnen Sie alle Entfernungen bei einer großen "Unendlichkeit", außer der Quelle bei 0. Finalisieren Sie dann n Mal den nächstgelegenen nicht besuchten Knoten und relaxieren Sie dessen ausgehende Kanten.
Probier es selbst
#include <stdlib.h>
int* dijkstra(int n, int* edges, int edges_size, int source, int* returnSize) {
// Hier Code schreiben
*returnSize = 0;
return edges;
}
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
Alle Lektionen in Dijkstra-Algorithmus - Graph-Algorithmen
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity