Lernziele

Rückblick VL 10: BFS — die Welle

BFS erkundet einen Graphen Ebene für Ebene (wie eine Welle im Wasser) und findet so den kürzesten Weg — gemessen in Anzahl Schritten.

Das Problem: Kanten haben ein Gewicht

In echten Karten ist nicht jede Straße gleich lang. Eine Kante trägt ein Gewicht — km, Minuten, Kosten. Und damit wählt BFS plötzlich falsch.

Erst die Intuition: wie ein Navi denkt

Bevor wir formal werden — stellt euch vor, ihr sucht die billigste Bahnverbindung von A zu allen anderen Orten. Wie würdet ihr von Hand vorgehen?

Dijkstra — die Idee

Wie BFS arbeitet Dijkstra mit einer „Welle" — aber sie wächst nicht nach Schritten, sondern nach aufsummierten Kosten. Jeder Knoten merkt sich seine bisher billigste bekannte Distanz zum Start.

Warum ist der billigste Knoten sofort „fertig"?

Das ist der eine geniale Trick von Dijkstra — und der Punkt, an dem die meisten kurz stocken. Schauen wir ihn uns ganz langsam an.

Das Herzstück: „Relax" einer Kante

„Relax" klingt kompliziert, ist aber nur ein Vergleich: Komme ich über meinen Nachbarn billiger ans Ziel als bisher? Wenn ja — neuen, besseren Wert eintragen.

// B hatte bisher dist = 4 (direkt von A).  Über C wären es nur 3:
if (dist[C] + gewicht(C, B) < dist[B]) {   // 1 + 2 < 4  ✓
    dist[B] = dist[C] + gewicht(C, B);     // dist[B] = 3
}

Unser Beispiel — ein gewichteter Graph

Fünf Orte A–E, die Zahlen an den Kanten sind die Kosten. Wir suchen die billigste Strecke von A zu jedem anderen Ort.

Die Distanz-Tabelle — der erste Schritt ganz langsam

Gleich kommt die volle Tabelle. Damit sie nicht erschlägt: So entsteht sie. Jede Spalte ist ein Knoten, jede Zeile ein „jetzt fertig". Das Zeichen ∞ heißt „noch kein Weg bekannt".

Dijkstra Schritt für Schritt

Wir führen eine Distanz-Tabelle. Grün = gerade verbessert (relaxed), blau = fertig (endgültig). Immer den kleinsten offenen Wert als Nächstes.

Das Ergebnis: die billigsten Wege

Dijkstra liefert die günstigste Distanz von A zu jedem Knoten — und die fett markierten Kanten bilden den Kürzeste-Wege-Baum.

BFS ist nur ein Spezialfall von Dijkstra

Die beiden sind keine Gegner — sie sind verwandt. Setzt man bei Dijkstra jedes Gewicht auf 1, kommt exakt BFS heraus.

n = Anzahl Knoten. Mit der Adjazenzliste aus VL 10 ist BFS linear — jeder Knoten und jede Kante genau einmal. Dijkstra (einfache Version) ist O(n²): es sucht n-mal unter n Knoten das kleinste → n × n. (Big-O wie in VL 4/5: 1, n, n², …)

Wo Dijkstra aussteigt: negative Kanten

Dijkstras Garantie („den Kleinsten abhaken ist endgültig") gilt nur, wenn Kanten nie negativ sind. Ein kleines Gegenbeispiel zeigt, warum.

🛠️ Jetzt bauen wir das in C — was muss Dijkstra sich merken?

Schaut auf die Tabelle von vorhin: Dijkstra muss zu jedem Knoten mehrere Dinge gleichzeitig festhalten. Bisher wären das viele lose Variablen.

char  name[5];
int   dist[5];
int   fertig[5];
// alle 3 beschreiben DIESELBEN Knoten,
// aber nichts im Code verbindet sie 😵

Werkzeug 1: struct — Daten bündeln

Ein struct ist ein selbst gebauter Datentyp: eine beschriftete Schublade mit Fächern. Perfekt, um alles zu einem Knoten an einem Ort zu halten.

typedef struct {
    char name;
    int  dist;     // billigste Distanz
    int  fertig;   // 0/1 = endgültig?
} Knoten;

Knoten k;
k.name = 'C';   k.dist = 1;   // Zugriff mit Punkt .

struct + Zeiger: der Pfeil ->

Sobald ihr (wie bei der Nachbarliste aus VL 10) einen Zeiger auf ein struct habt, schreibt man statt des Punkts den Pfeil ->.

Knoten  k;     k.dist  = 1;  // Variable → .
Knoten *p=&k;   p->dist = 1;  // Zeiger   → ->

Werkzeug 2: malloc — Speicher zur Laufzeit

Ein Array braucht seine Größe im Voraus: Knoten netz[100];. Aber wie viele Orte hat die Karte? Oft weiß man das erst beim Laufen (z. B. aus einer Datei). Lösung: Speicher auf Bestellung.

malloc benutzen — Schritt für Schritt

#include <stdlib.h>   // hier wohnen malloc & free

// Platz für n Knoten holen (n erst zur Laufzeit bekannt):
Knoten *netz = malloc(n * sizeof(Knoten));

if (netz == NULL) { return 1; }  // kein Platz? → abbrechen (VL10: NULL!)

netz[2].dist = 1;       // benutzen wie ein normales Array

free(netz);              // am Ende IMMER zurückgeben

Stolpersteine in C — die drei Klassiker

struct, Zeiger und malloc sind mächtig — und genau hier passieren die häufigsten Fehler. Diese drei erkennt ihr ab jetzt sofort.

// p ist ein Zeiger!
p.dist = 1;   ❌
p->dist = 1;  ✅

x = malloc(...);
// ... benutzen ...
free(x);  ✅

p = malloc(...);
if (p == NULL) ...
p->dist = 1; // erst danach

Alles zusammen: die Nachbarliste aus VL 10

Mit beiden Werkzeugen verwandeln wir das gemalte C ──► A ──► B ──► ∅ in echten Code: ein struct bündelt Nachbar + Gewicht + Zeiger, malloc legt jeden Knoten an.

typedef struct Kante {
    int ziel;            // Nachbar-Index
    int gewicht;         // Kosten der Kante
    struct Kante *next;  // nächster Nachbar
} Kante;

Kante *e = malloc(sizeof(Kante)); // Platz fuer EINE Kante holen
e->ziel    = 2;    // diese Kante fuehrt zu Knoten 2 (= C)
e->gewicht = 1;    // sie kostet 1
e->next    = NULL; // dahinter kommt (noch) kein Nachbar → Listenende

🤔 Mini-Quiz

🤔 Mini-Quiz — Runde 2

Zusammenfassung — in einer Slide

📚 Quellen & zum Ausprobieren