Graph-kürzester Pfad |
30.01.2007, 16:44 | nicki001 | Auf diesen Beitrag antworten » | ||
Graph-kürzester Pfad 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? |
||||
30.01.2007, 17:06 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Graph-kürzester Pfad
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 |
||||
30.01.2007, 17:15 | 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?? |
||||
30.01.2007, 17:31 | Abakus | Auf diesen Beitrag antworten » | ||
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 |
||||
30.01.2007, 17:53 | nicki001 | Auf diesen Beitrag antworten » | ||
ja, aber mehr als ich da geschrieben hab, steht nicht in der aufgabe.. |
||||
30.01.2007, 18:12 | Abakus | Auf diesen Beitrag antworten » | ||
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 |
||||
Anzeige | ||||
|
||||
30.01.2007, 18:21 | 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. |
||||
30.01.2007, 18:45 | 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 |
||||
30.01.2007, 18:56 | 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..) |
||||
30.01.2007, 19:09 | 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 |
||||
30.01.2007, 19:22 | 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 |
||||
30.01.2007, 19:25 | 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.. |
||||
30.01.2007, 20:12 | Abakus | Auf diesen Beitrag antworten » | ||
Du hast die Wahl, die Aufgabe noch genauer abzuklären (bietet sich an) , oder dich mit möglicherweise verschiedenen Algorithmen zu befassen, die unter verschiedenen Voraussetzungen jeweils kürzeste Wege berechnen. Grüße Abakus |
||||
30.01.2007, 20:48 | 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 |
||||
30.01.2007, 23:48 | 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 Du kannst dir wahlweise Algorithmen vornehmen: - Dijkstra - Bellmann-Ford - Floyd & Warshall - usw. Grüße Abakus |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |