Gewichteter Graph ist ein Graph, bei dem jeder Kante (manchmal auch jedem Knoten) ein Zahlenwert zugeordnet ist – das Gewicht. Es steht für Kosten, Distanz, Zeit, Kapazität oder eine andere messbare Größe der Verbindung. Ein ungewichteter Graph ist der Spezialfall, in dem alle Kanten das gleiche Gewicht tragen (meist 1); die Unterscheidung ist zentral, weil viele Algorithmen nur auf gewichteten oder nur auf ungewichteten Graphen arbeiten.
Darstellung
- Adjazenzmatrix: Statt der Einträge 0/1 stehen an Position (i, j) die Gewichte der Kante von Knoten i zu Knoten j; ein fehlender Eintrag markiert „keine Kante“.
- Adjazenzliste: Jeder Nachbar wird zusammen mit seinem Kantengewicht gespeichert, etwa als Paar (Nachbar, Gewicht) – platzsparender für dünn besetzte Graphen.
Beide Darstellungen werden in den Artikeln Adjazenzmatrix und Adjazenzliste ausführlich behandelt.
Wichtige Algorithmen
- Kürzeste Wege: Der Dijkstra-Algorithmus findet kürzeste Wege in Graphen mit nicht-negativen Gewichten; der Bellman-Ford-Algorithmus beherrscht zusätzlich negative Gewichte.
- Minimaler Spannbaum: Kruskal und Prim berechnen kostengünstigste Verbindungen, indem sie die Summe der Kantengewichte minimieren.
- Netzwerkflüsse: Max-Flow-Algorithmen nutzen Kantenkapazitäten als Gewichte.
Wichtig: Bei negativen Gewichten versagt der Dijkstra-Algorithmus (er geht davon aus, dass jeder Zwischenschritt die Weglänge nicht verringert). Solche Fälle gehören zu Bellman-Ford.
Anwendungen
- Routing: Straßenkarten mit Streckenlängen, Verkehrszeiten oder Treibstoffkosten als Gewichte
- Netzwerktopologie: Latenz oder Bandbreite zwischen Servern als Kantenwerte
- Aufgabenplanung: Abhängigkeiten mit Dauer-Gewichten, etwa in einem DAG bzw. gerichteten Graphen
Das Gewichtskonzept ist unabhängig von der Richtung: Sowohl ungerichtete als auch gerichtete Graphen können gewichtet sein.