Graph-kürzester Pfad

Neue Frage »

nicki001 Auf diesen Beitrag antworten »
Graph-kürzester Pfad
hi,
Ich bearbeite gerade folgende Aufgabe:

Gegeben sei ein ungerichteter zusammenhängender Graph G mit einem ausgezeichneten Knoten a.
Sie sollen für Anfrageknoten x,y einen kurzesten Pfad (kann Knoten mehrfach besuchen) berechnen, der von x über a nach y führt.
Warum existiert der und wie rechnen Sie ihn (algorithmisch)aus?


Warum er exisitiert:

Laut Def. ist ein ungerichteter Graph G(V,E) zusammenhängend, wenn es für zwei beliebige Knoten x,y element V einen ungerichteten Weg gibt.

Das bedeutet doch nichts anderes, als das man jeden Knoten von jedem aus Knoten aus erreichen kann.
Deshalb gibt es mehrere Wege (über mehrere Knoten) von x nach y, also gibt es auch mehrere Knoten über a und deshalb gibt es auch einen kürzesten.


Berechnung algorithmisch:

das ist doch der Dijkstra-Algorithmus oder? bin mir nicht sicher...

Stimmt das alles so was ich geschrieben hab?
Abakus Auf diesen Beitrag antworten »
RE: Graph-kürzester Pfad
Zitat:
Original von nicki001
Berechnung algorithmisch:

das ist doch der Dijkstra-Algorithmus oder? bin mir nicht sicher...


Solange du keine negativen Kantengewichte hast, kannst du den nehmen.

Für Algorithmus-Fragen ist ansonsten das Informatiker-Bord einen Blick wert.

Grüße Abakus smile
nicki001 Auf diesen Beitrag antworten »

ja hmmm ok, aber mich stört das man noch über a muss... also müsste der algorithmus erst den kürzesten pfad von x zu a und dann den kürzesten pfad von a zu y ermitteln oder??

Ist denn mein beschreibung für den ersten Teil der Aufgabe richtig??
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von nicki001
Ist denn mein beschreibung für den ersten Teil der Aufgabe richtig??


Es fehlen in der Aufgabe Voraussetzungen: ohne dass gesagt wird, wie die Kantengewichtungen definiert sein sollen bzw. ob es überhaupt welche gibt, ist nicht klar, was ein kürzester Weg sein soll.

Grüße Abakus smile
nicki001 Auf diesen Beitrag antworten »

ja, aber mehr als ich da geschrieben hab, steht nicht in der aufgabe..
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von nicki001
ja, aber mehr als ich da geschrieben hab, steht nicht in der aufgabe..


Dann ist die Aufgabe "Murks", weil ja irgendwie Entfernungen gegeben sein müssen, wenn denn schon nach einer kürzesten Entfernung gefragt ist.

Denkbar wäre noch, alle Kanten mit dem Gewicht 1 zu bewerten; aber besser du stellst erstmal fest, wie das mit den Entfernungen wirklich genau gemeint ist.

Grüße Abakus smile
 
 
nicki001 Auf diesen Beitrag antworten »

naja also ich denke man soll nich wirklich was rechnen...sondern eher so allgemein erklären, warum es einen kürzesten weg gibt und dann wie man den berechnen könnte.
Abakus Auf diesen Beitrag antworten »

Ja, das ändert ja nichts. Du brauchst einen bewerteten Graphen (oder bewerteten Digraphen) für sowas, also ein Graph G = (K, E, g), wobei K die Menge der Knoten, die Menge der Kanten, und eine Kantenbewertung ist.

Hat g nur nichtnegative Werte, lässt sich Dijkstra's Algorithmus verwenden.

Hier fehlt einfach die Funktion g in der Aufgabe, deshalb ist das zu klären.

Nehmen wir an, du hast so eine nichtnegative Funktion g. Dann ex. wegen des Zusammenhangs ein Weg von x nach a und von a nach y.

Ist nun zB K endlich und enthält keine parallelen Kanten, so existiert auch ein kürzester Weg, ja (schließlich gibt es nur endlich viele solcher Wege ohne Zykel).

Grüße Abakus smile
nicki001 Auf diesen Beitrag antworten »

ja also ich denke die kanten sind bewertet, sonst is ja die aufgabe sinnlos, und man soll glaube nix beweisen oder so, sondern einfach nur sagen wieso es überhaupt sowas wie ein kürzesten weg geben kann (und wieso nicht alles gleich sind..)
nick001 Auf diesen Beitrag antworten »

äääähm aber die kannten müssen garnicht bewertet sein, merke ich gerade.

Denn der BFS (Breitsuche) algorithmus, durchläuft ja den grapf und bewertet ihn..hmm ob das mit der aufgabe zu tun hat...wer weiss
Abakus Auf diesen Beitrag antworten »

Deinen Kontext zu der Aufgabe kenne ich nun nicht. Wenn da vorher ein BFS irgendwas (?) macht, ok.

Für den Dijkstra-Algorithmus hast du bei Wiki jedenfalls ein Beispiel: hier.

Grüße Abakus smile
nick001 Auf diesen Beitrag antworten »

ne also die aufgabe lautet wirklich nur so:

Gegeben sei ein ungerichteter zusammenhängender Graph G mit einem ausgezeichneten Knoten a.
Sie sollen für Anfrageknoten x,y einen kurzesten Pfad (kann Knoten mehrfach besuchen) berechnen, der von x über a nach y führt.
Warum existiert der und wie rechnen Sie ihn (algorithmisch)aus?

Wobei ich denke nur der letzte satz gehört zur fragestellung..
Abakus Auf diesen Beitrag antworten »

Du hast die Wahl, die Aufgabe noch genauer abzuklären (bietet sich an) Augenzwinkern , oder dich mit möglicherweise verschiedenen Algorithmen zu befassen, die unter verschiedenen Voraussetzungen jeweils kürzeste Wege berechnen.

Grüße Abakus smile
nick001 Auf diesen Beitrag antworten »

hööö? was soll ich machen??

ich kann doch nix machen, die aufgabe steht so da, wie sie da steht, fragen kann ich auch niemanden.. (heut war letztes tutorium) maaaaaan unglücklich
Abakus Auf diesen Beitrag antworten »

Ich nehme mal an, dass ihr das Gebiet irgendwie behandelt habt und du auch etwa weißt, was für die Aufgabe erwartet wird.

Ansonsten... dumm gelaufen verwirrt

Du kannst dir wahlweise Algorithmen vornehmen:

- Dijkstra

- Bellmann-Ford

- Floyd & Warshall

- usw.

Grüße Abakus smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »