Einen Algorithmus mit passender Laufzeit konstruieren

Question

Aufgabe:

Sei \( G=(V, E, \Psi) \) ein gerichteter Graph mit Kantengewichten \( c_{e}, e \in E \), und seien \( s, t \in V \) zwei Knoten.

Konstruieren Sie einen Algorithmus mit Laufzeit \( O(|V| \cdot|E|) \), welcher überprüft, ob ein kürzester Pfad von \( s \) nach \( t \) existiert.

Problem/Ansatz:

Hey hat jemand eine Idee wie ich es schreiben, ich weiss garnicht wie das mit der Laufzeit ablauft. (Bin neu und weiss leider noch nicht ob man auch solche Aufgaben hier hochladen kann)

Answer 1

Ein kürzester Pfad von \( s \) nach \( t \) existiert genau dann, wenn ein Pfad von \(s\) nach \(t\) existiert.

Konstruiere also einen Algorithmus mit Laufzeit \( O(|V| \cdot|E|) \), welcher überprüft, ob ein Pfad von \( s \) nach \( t \) existiert.

Comments

Hä wie soll mir das helfen? Du hast mir nochmal die Aufgabenstellung hingeschrieben. :/

---

Das habe ich nicht. Vergleiche noch mal ganz genau deine Auifgabe mit meinem Lösungsvorschlag.