0 Daumen
441 Aufrufe

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)

Avatar von

1 Antwort

0 Daumen

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.

Avatar von 107 k 🚀

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community