Der Dijkstra-Algorithmus ist ein Algorithmus, der verwendet wird, um das Problem des kürzesten Pfades in einem Diagramm zu lösen. Dies bedeutet, dass der Dijkstra-Algorithmus bei einer Anzahl von Knoten und den Kanten zwischen ihnen sowie der “Länge” der Kanten (als “Gewicht” bezeichnet) den kürzesten Weg vom angegebenen Startknoten zu allen anderen Knoten findet.

Beschreibung des Algorithmus

Das Grundprinzip des Dijkstra-Algorithmus besteht darin, den Knoten mit dem derzeit kleinsten Abstand zur Quelle iterativ zu betrachten und alle noch nicht besuchten Nachbarn zu aktualisieren, wenn der Pfad zu ihm über den aktuellen Knoten kürzer ist. Im Einzelnen führt dies zu den folgenden Schritten:

1. Initialisieren Sie den Abstand zum Startknoten als 0 und den Abstand zu allen anderen Knoten als unendlich
2. Setzen Sie alle Knoten auf “nicht besucht”.

3. Während wir nicht alle Knoten besucht haben:

   1. Suchen Sie den Knoten mit der aktuell kürzesten Entfernung von der Quelle (beim ersten Durchgang ist dies der Quellknoten selbst).
   2. Überprüfen Sie für alle Knoten daneben, die wir noch nicht besucht haben, ob die derzeit kleinste Entfernung zu diesem Nachbarn größer ist, als wenn wir über den aktuellen Knoten gehen würden
   3. Wenn dies der Fall ist, aktualisieren Sie die kleinste Entfernung dieses Nachbarn auf die Entfernung von der Quelle zum aktuellen Knoten plus die Entfernung vom aktuellen Knoten zu diesem Nachbarn

Am Ende enthält das Array, mit dem wir die aktuell kürzeste Entfernung von der Quelle zu allen anderen Knoten verfolgt haben, die (endgültigen) kürzesten Entfernungen.

Beispiel des Algorithmus

Betrachten Sie das folgende Diagramm:

Die Schritte, die der Algorithmus in diesem Diagramm ausführt, wenn der Knoten 0 als Startpunkt angegeben wird, sind:

1. Besuche Knoten 0
2. Aktualisieren der Entfernung von Knoten 1 bis 3
3. Aktualisieren des Abstands von Knoten 2 zu 1
4. Besuchte Knoten: 0
5. Derzeit niedrigste Entfernungen: [0, 3, 1, unendlich, unendlich, unendlich]

6. Besuch von Knoten 1 mit der aktuellen Entfernung 1

   • Aktualisieren der Entfernung von Knoten 3 bis 5
   • Besuchte Knoten: 0, 2
   • Derzeit niedrigste Entfernungen: [0, 3, 1, 5, unendlich, unendlich]

7. Besuch von Knoten 3 mit der aktuellen Entfernung 3

   • Aktualisieren der Entfernung von Knoten 4 bis 4
   • Besuchte Knoten: 0, 1, 2
   • Derzeit niedrigste Entfernungen: [0, 3, 1, 5, 4, unendlich]

8. Besuche Knoten 4 mit der aktuellen Entfernung 4

   • Aktualisieren der Entfernung von Knoten 5 bis 5
   • Besuchte Knoten: 0, 1, 2, 4
   • Derzeit niedrigste Entfernungen: [0, 3, 1, 5, 4, 5]

9. Besuche Knoten 5 mit aktueller Entfernung 5

   • Keine zu aktualisierenden Entfernungen
   • Besuchte Knoten: 0, 1, 2, 3, 4
   • Derzeit niedrigste Entfernungen: [0, 3, 1, 5, 4, 5]

10. Besuch des Knotens 5 mit der aktuellen Entfernung 5

    • Keine zu aktualisierenden Entfernungen
    • Besuchte Knoten: 0, 1, 2, 3, 4, 5

Alle besuchten Knoten Letzte niedrigste Abstände: [0, 3, 1, 5, 4, 5]

Laufzeit des Algorithmus

Die Laufzeitkomplexität von Dijkstra hängt davon ab, wie es implementiert wird. Wenn ein Min-Heap verwendet wird, um den nächsten zu besuchenden Knoten zu bestimmen, und die Adjazenz unter Verwendung von Adjazenzlisten implementiert wird, ist die Laufzeit O(| E | + | V | log | V|) (|V| = Nummer Anzahl der Knoten, |E| = Anzahl der Kanten). Wenn wir einfach alle Entfernungen durchsuchen, um den Knoten mit der niedrigsten Entfernung in jedem Schritt zu finden, und mithilfe einer Matrix nachsehen, ob zwei Knoten benachbart sind, steigt die Laufzeitkomplexität auf O(| V | ^ 2).

Speicherkomplexität des Algorithmus

Die Speicherkomplexität von Dijkstra hängt auch davon ab, wie es implementiert ist, und entspricht der Laufzeitkomplexität.

C ist eine kompilierte Sprache, die für viele Zwecke verwendet wird, obwohl sie hauptsächlich in Systemen zu finden ist, in denen Wichtigkeit wichtig ist. Dies liegt daran, dass C viel Unterstützung auf niedriger Ebene für die Optimierung bietet, auf Kosten der Tatsache, dass einige der praktischen Abstraktionen, die andere Sprachen bieten, nicht vorhanden sind. C tritt daher hauptsächlich in Situationen auf, in denen die verfügbare Rechenleistung gering ist, wie beispielsweise eingebettete Systeme, oder in Situationen, in denen die erforderliche Rechenleistung hoch ist, wie z. B. Simulation oder Deep Learning.

“Hello World” in C

Das Wichtigste zuerst - hier erfahren Sie, wie Sie Ihre erste Codezeile in C ausführen können.

1. Wenn Sie unter Linux oder Mac arbeiten, laden Sie die neueste Version von GCC, einem C-Compiler, von gcc.gnu.org herunter und installieren Sie sie. Sie können auch eine frühere Version herunterladen, wenn Ihr Anwendungsfall dies erfordert.
2. Wenn Sie unter Windows arbeiten, können Sie auch GCC installieren, obwohl dies zu Problemen führen kann. Sie haben auch andere Optionen, z. hier.

3. Öffnen Sie ein Terminal, stellen Sie sicher, dass der Befehl gcc funktioniert (oder der entsprechende Befehl für den von Ihnen verwendeten Compiler) und dass sich der Befehl, den Sie verwenden werden, auf die Version bezieht, die Sie gerade durch Ausführen installiert haben gcc --version. Wenn der Fehler “Befehl nicht gefunden” (oder ähnlich) angezeigt wird, starten Sie die Befehlszeile und, falls dies nicht hilft, Ihren Computer neu. Wenn das Problem weiterhin besteht, finden Sie hier einige hilfreiche Forumfragen für jede Plattform:

   • Windows
   • Mac
   • Linux

4. Sobald dies funktioniert, kopieren Sie das folgende Snippet in eine Datei mit dem Namen HelloWorld.c:

   #include<stdio.h>
   int main() {
   printf("Hello World\n");
   return 0;
   }

5. Ändern Sie das Verzeichnis, indem Sie “cd path / to / HelloWorld” eingeben, dann “gcc HelloWorld.c” ausführen, um die Datei zu kompilieren (die den Bytecode erstellt), und dann “. / A.out” ausführen. Dies sollte “Hello World” auf Ihrem Terminal drucken.

Das ist es! Personen, die mehrere Programmiersprachen kennen, werden feststellen, dass die Eintrittsbarriere in C etwas niedriger ist als in Java, obwohl sie niedriger ist, während die Eintrittsbarriere für Python niedriger ist, obwohl sie höher ist. Meine persönliche Beobachtung ist, dass Sprachen auf niedriger und hoher Ebene tendenziell niedrige Eintrittsbarrieren aufweisen, während Sprachen auf mittlerer Ebene höhere Barrieren aufweisen.

Grundlagen in C

Um in C implementierte Algorithmen und Technologien zu verstehen, muss man zunächst verstehen, wie grundlegende Programmierkonzepte in dieser bestimmten Sprache aussehen. Jedes der folgenden Snippets sollte mit den oben genannten Befehlen kompiliert und ausgeführt werden.

Variablen und Arithmetik

Variablen in C sind statisch typisiert, was bedeutet, dass der Inhalt einer Variablen beim Schreiben des Codes angegeben werden muss. Der Datentyp für ganze Zahlen ist beispielsweise “int”. Zahlen mit Dezimalstellen werden je nach erforderlicher Genauigkeit mit “float” oder “double” eingegeben. Der Typ für Text ist “String”.

#include<stdio.h>

int main() {
    int number = 5;
    double decimalNumber = 3.25;
    double result = number * decimalNumber;
    char callout [] = "The number is ";
    // In this instance, the values are concatenated rather than added because one of them is a String.
    printf("%s", callout);
    printf("%f", result);
    printf("\n");
    return 0;
}

Arrays

Arrays in C sind real Arrays (im Gegensatz zu beispielsweise Python, wo sie als Listen implementiert sind). Dies hat zur Folge, dass die Größe beim Erstellen festgelegt werden muss und nicht geändert werden kann, aber auch, dass sie in C effizienter sind als in Python. Im Gegensatz zu Java überprüft C auch keine Array-Grenzen. Wenn Sie auf einen Index zugreifen, der nicht vorhanden ist, liest das Programm alles, was sich an dieser Stelle im Speicher befindet (was wahrscheinlich Kauderwelsch sein wird).

int integers[5];
integers[3] = 12; // Assigning values to positions in the array
printf("%d\n", integers[0]); // will be 0
printf("%d\n", integers[3]); // will be 12
printf("%d\n", integers[6]); // will print something random that happened to be at that location in memory
return 0;

Bedingungen

Wie die meisten Programmiersprachen kann C “if-else” -Anweisungen ausführen. Zusätzlich kann C auch “switch-case” -Anweisungen ausführen.

int value = 5;
    if(value == 5){
        printf("%s\n", "Value is 5");
    } else if(value < 5){
        printf("%s\n", "Value is less than 5");
    } else {
        printf("%s\n", "Value is something else");
    }
    
    switch (value){
        case 1:
            printf("%s\n", "Value is 1");
            break; // Don't go further down the cases
        case 2:
            printf("%s\n", "Value is 2");
            break; // Don't go further down the cases
        case 3:
            printf("%s\n", "Value is 3");
            break; // Don't go further down the cases
        case 4:
            printf("%s\n", "Value is 4");
            break; // Don't go further down the cases
        case 5:
            printf("%s\n", "Value is 5");
            break; // Don't go further down the cases
        default:
            printf("%s\n", "Value is something else");
    }

Der obige C-Code gibt zweimal “Wert ist 5” aus.

Schleifen

C unterstützt “for” -, “while” - und “do while” -Schleifen. Die Anweisungen break undcontinue werden ebenfalls unterstützt. Das folgende Beispiel zeigt die Unterschiede:

int value = 2;
for (int i = 0; i < value; i++) {
    printf("%d\n", i);
}
while (value > 0) {
    printf("%d\n", value);
    value--;
}
do {
    printf("%d\n", value);
    value--;
} while (value > 0);

Dadurch wird Folgendes auf das Terminal gedruckt:

0
1
2
1
0

Beachten Sie die letzte “0”: Sie wird gedruckt, weil in der “do-while” -Schleife im Vergleich zur “while” -Schleife. Der Codeblock wird mindestens einmal ausgeführt, bevor die Bedingung überprüft wird.

Funktionen

Funktionen in C können ähnlich wie Java deklariert werden, erfordern jedoch weniger Boilerplate, da sie nicht Teil von Klassen oder Objekten sein müssen. Hier ist ein minimales Beispiel für eine Funktion:

#include<stdio.h>

int addNumbers(int numberOne, int numberTwo) {
    return numberOne + numberTwo;
}

int main() {
    printf("%d\n", addNumbers(3, 4));
}

Syntax

C erfordert die Verwendung von geschweiften Klammern ({}), um Codeblöcke in Bedingungen, Schleifen, Funktionen usw.; Außerdem sind am Ende der Anweisungen Semikolons erforderlich. Dies kann zwar zu lästigen Syntaxfehlern führen, bedeutet jedoch auch, dass die Verwendung von Leerzeichen für die bevorzugte Formatierung (z. B. Einrücken von Codeteilen) den Code nicht beeinflusst. Beachten Sie, dass die Syntax von C Java sehr ähnlich ist. Die Syntax von Java und viele andere Sprachen, die nach C kamen und / oder von C abgeleitet wurden, kopieren viele Aspekte seiner Syntax.

Fortgeschrittenes Wissen zu C

C wurde erstmals 1972 veröffentlicht, ist statisch typisiert und wurde mit verschiedenen Implementierungen auf viele Plattformen portiert (eine davon ist GCC, die in diesem Artikel vorgestellt wurde). Für weitere Informationen hat C einen großartigen Artikel Wikipedia.