Azyklische Graphen, Algorithmus

Question

Sei G = (V,E,W) ein azyklischer, gerichteter, gewichteter Graph.

a) Entwerfen Sie einen Algorithmus, der den längsten Pfad (bezüglich der Gewichte) in G in Zeit O(|V|+|E|)
berechnet.

b) Entwerfen Sie einen Algorithmus, der die Anzahl der Pfade in G in Zeit O(|V| + |E|) berechnet. Beachten
Sie hierbei auch leere Pfade.

!!

Answer 1

Kannst du erklären was der folgende Algorithmus macht?

Comments

Wenn die Kante, die man aktuell durchläuft, größer ist als die Kante die davor gespeichert wurde wird diese als die aktuelle Kante gesetzt und v wird aktueller Knoten.

Stimmt nicht ganz oder?

---

Doch, es ist richtig.

---

Also ist das die Aufgabe a) oder?

---

Ja, genau so ist es. :)