Netzwerkoptimierung: Dijkstra, Ford-Fulkerson, CPM & PERT

Der Dijkstra-Algorithmus findet den kürzesten Weg von einem Startknoten zu allen anderen Knoten in einem gewichteten Graphen mit nicht-negativen Kantengewichten. Er wird häufig in der Routenplanung und Netzwerkoptimierung eingesetzt. Der Algorithmus arbeitet schrittweise und garantiert optimale Lösungen.

Der Ford-Fulkerson-Algorithmus berechnet den maximalen Fluss in einem Flussnetzwerk zwischen einer Quelle und einer Senke. Er sucht iterativ nach erweiternden Pfaden und erhöht den Fluss entlang dieser Pfade, bis kein weiterer Pfad mehr gefunden werden kann. Das Ergebnis entspricht dem max-flow min-cut Theorem.

CPM (Critical Path Method) verwendet deterministische Zeitschätzungen für Aktivitäten, während PERT (Program Evaluation and Review Technique) mit probabilistischen Zeitschätzungen arbeitet. Beide Methoden dienen der Projektplanung und identifizieren kritische Pfade. PERT berücksichtigt zusätzlich Unsicherheiten durch drei Zeitschätzungen pro Aktivität.

Der kritische Pfad ist die längste Kette von Aktivitäten in einem Projektnetzplan, die die Mindestprojektdauer bestimmt. Aktivitäten auf dem kritischen Pfad haben keinen Pufferzeit und jede Verzögerung verlängert das gesamte Projekt. Die Identifikation des kritischen Pfads ist essentiell für effektives Projektmanagement.

Der Graph muss gewichtet sein und alle Kantengewichte müssen nicht-negativ sein, da der Algorithmus sonst nicht korrekt funktioniert. Zudem sollte der Graph zusammenhängend sein, damit alle Knoten erreicht werden können. Bei negativen Gewichten muss stattdessen der Bellman-Ford-Algorithmus verwendet werden.