Question 1

Was ist der Dijkstra-Algorithmus und wofür wird er verwendet?

Accepted Answer

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.

Question 2

Wie funktioniert der Ford-Fulkerson-Algorithmus?

Accepted Answer

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.

Question 3

Was ist der Unterschied zwischen CPM und PERT?

Accepted Answer

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.

Question 4

Was versteht man unter dem kritischen Pfad in der Netzplantechnik?

Accepted Answer

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.

Question 5

Welche Voraussetzungen müssen für die Anwendung des Dijkstra-Algorithmus erfüllt sein?

Accepted Answer

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.

Netzwerkoptimierung: Dijkstra, Ford-Fulkerson, CPM & PERT

Lernkarten zu Netzwerkoptimierung