Lernziele

Wo wir stehen — und der Plan für heute

Erst das Bild: Dijkstra als Flussdiagramm

Pseudocode liest sich abstrakt — deshalb zuerst der Fluss. Der Kern ist eine Schleife: schnapp dir den billigsten offenen Knoten, verbessere seine Nachbarn, wiederhole.

Dijkstra als Pseudocode — sprachunabhängig

Zuerst der Algorithmus ohne Sprache. Wer in Python, Java oder Rust programmiert, kann das 1:1 übersetzen — die Idee ist überall gleich.

u = aktueller (billigster) Knoten  ·  v = ein Nachbar von u  ·  w = Gewicht der Kante u→v  ·  dist[x] = billigste bekannte Distanz zu x  ·  fertig[x] = schon endgültig abgehakt? (Start: alle false)  ·  offen = noch nicht fertig

Von Pseudocode zu C — was brauchen wir?

Das ganze Dijkstra auf einen Blick

Kein Lab zum Üben — deshalb einmal kompakt statt in Häppchen: das komplette Programm mit den drei Schritten markiert. Ihr müsst es nicht auswendig tippen, sondern lesen können.

typedef struct Kante { int ziel, gewicht; struct Kante *next; } Kante;

int dist[N], fertig[N], start = 0;
// (1) INIT: alles unbekannt (INF), Start = 0
for (int i = 0; i < N; i++) { dist[i] = INF; fertig[i] = 0; }
dist[start] = 0;

for (int schritt = 0; schritt < N; schritt++) {
    // (2) billigsten OFFENEN Knoten u waehlen
    int u = -1;
    for (int i = 0; i < N; i++) {
        if (fertig[i])      continue;   // schon abgehakt
        if (dist[i] == INF) continue;   // unerreichbar
        if (u == -1 || dist[i] < dist[u]) // erster ODER billiger?
            u = i;
    }
    if (u == -1) break;   // nichts Offenes mehr -> fertig
    fertig[u] = 1;

    // (3) RELAX: Nachbarn von u ueber die Kanten verbessern
    for (Kante *e = adj[u]; e != NULL; e = e->next)
        if (dist[u] + e->gewicht < dist[e->ziel])
            dist[e->ziel] = dist[u] + e->gewicht;
}

Es läuft — und findet clevere Umwege

Start A: das Programm gibt für jeden Knoten die kürzeste Distanz aus.

A -> A: 0
A -> B: 3      // via C, nicht direkt!
A -> C: 1
A -> D: 4
A -> E: 7

Wozu das Ganze? Dijkstra in der echten Welt

Derselbe Algorithmus, den ihr gerade gelesen habt, läuft milliardenfach am Tag:

Der Flaschenhals: warum O(n²)?

Erinnerung aus VL 5: Was heißt O(…)?

Big-O hattet ihr schon in VL 5 — hier die Kurz-Auffrischung, weil wir es gleich für Dijkstra brauchen. Es beschreibt, wie die Laufzeit wächst, wenn die Eingabe größer wird — nicht die genaue Zeit in Sekunden.

Wie stark ist der Unterschied wirklich?

Angenommen, ein Schritt dauert 1 Nanosekunde. So viele Schritte braucht jede Komplexität bei wachsendem n:

Die Lösung: eine Priority Queue

Wir tauschen das „jedes Mal alle durchsuchen" gegen eine clevere Warteschlange, die uns den Kleinsten sofort gibt.

Kurz erklärt: der Min-Heap

Warum ist ein Baum nur log n hoch?

log n klingt abstrakt — ist aber ganz einfach: „Wie oft muss ich verdoppeln, um von 1 bis n zu kommen?" Genau das schauen wir jetzt an.

Verdopplungs-Leiter — zähle die Schritte:

Von 1 bis 1 000 000 sind es nur 20 Verdopplungen → log₂(1 000 000) ≈ 20.

Dijkstra mit Priority Queue: der Gewinn

V = Knoten, E = Kanten. (Den Min-Heap selbst zu bauen ist ein eigenes Thema — Idee & Nutzen zählen hier.)

Wann lohnt sich Optimieren — und wann nicht?

Schneller ist nicht immer besser. Der Heap lohnt sich nicht überall:

Optimieren — das übertragbare Rezept

Was wir bei Dijkstra gemacht haben, ist ein allgemeines Muster — für jedes Programm:

🤖 Teil 2: Automatisierung

Beim Entwickeln macht ihr dieselben Schritte immer wieder: kompilieren, starten, testen. Automatisierung heißt: einmal aufschreiben, der Rechner wiederholt es.

Was lohnt sich zu automatisieren?

Nicht alles — aber drei Arten von Aufgaben schreien geradezu danach:

Wie Firmen Software ausliefern: die Pipeline

In echten Firmen macht niemand mehr „bauen, testen, hochladen" von Hand. Jede Code-Änderung läuft automatisch durch eine Kette — die CI/CD-Pipeline.

CI, Delivery, Deployment — die drei Stufen

„CI/CD" sind eigentlich drei Ausbaustufen — jede automatisiert einen Schritt mehr:

Welche Tests gibt es? Die Testpyramide

Im „Test"-Schritt der Pipeline stecken mehrere Arten von Tests — von klein & schnell bis groß & langsam:

Was die CI sonst noch automatisch prüft

„Funktioniert es?" ist nur der Anfang. Moderne Pipelines prüfen bei jedem Commit auch:

So automatisieren Tech-Firmen

Automation gibt es überall — nicht nur bei IT-Firmen

Ein Feature geht live — in Minuten statt Wochen

So fließt heute eine kleine Änderung durch eine Firma — fast ohne Handarbeit:

Warum Firmen so viel automatisieren

Die Werkzeuge — grob eingeordnet

Ihr müsst sie hier nicht können — nur wissen, dass es sie gibt und wofür sie da sind:

Faustregeln für Automatisierung

Zusammenfassung — in einer Slide

Was ihr jetzt könnt — ein ganzes Semester

Das war die letzte inhaltliche Vorlesung. Schaut, wie weit ihr gekommen seid: