Dijkstra: Aufgabe richtig verstanden?

Ich sitze gerade an einer Aufgabe und bin total verwirrt was überhaupt die Aufgabe ist: Hier ist die Aufgabe

So wie ich das verstanden habe, soll ich die größte Kante im günstigsten Pfad finden. Ist das richtig? Wenn ich mir die Musterlösung anschaue scheint es, dass nach der kleinsten Kante im teuersten Pfad gefragt wird. Ich bin verwirrt und würde mich über Aufklärung sehr freuen

Gruß

Answer 1

[RIDDICC]

also ich würd sagen, dass du zu jedem Knoten v denjenigen Weg vom Startknoten s bis zum Knoten v finden sollst, dessen längste Teilstrecke (Kante) möglichst kurz ist...

also: die Gesamtlänge des Weges ist ohne Belang... wichtig ist nur, dass die einzelnen Kanten möglichst kurz sind, und dass man trotzdem bei v ankommt... kicher

Woher ich das weiß: Studium / Ausbildung – Diplom(U)-Informatik-Studium erfolgreich absolviert...

Comments

[redsky]

jaaaa ja ok also ich hab kurz ein Beispiel zusammengestellt und als seperate Antwort hochgeladen. Magst du das kurz bestätigen was ich da zusammengeschrieben habe? Also wenns stimmt natürlich nur :D

Answer 2

[redsky]

ok also nehmen wir mal dieses Beispiel als Graphen:

der günstigste Weg zum Knoten b wäre eigentlich s -> a -> b f(b) = 4.

Aaaber ich soll den Algo so schreiben das er einen Weg nimmt der immer die günstigsten Kanten nimmt, also s->c->d->e->a->b f(b)=5. So ne?

Comments

[RIDDICC]

1. ja...
2. aber: was ist f(b)? die Summe der Kantenlängen des Pfades?
3. wichtig ist vor Allem: m(P1)=3 und m(P2)=1
4. wobei P1 der günstigste Pfad (sab) und P2 der zweite von dir genannte Pfad (scdeab) ist...
5. also ist m(b)=m(P2)=1
6. stümmt's?

[redsky]

@RIDDICC

ja ok ich verstehe es.

Letzte Frage: m(v)= min{m(P): P ist ein s-v-Weg}

bedeutet also übersetzt: Die längste Kante von s nach v soll minimal gehalten werden.

[RIDDICC]

@redsky

naja... kann man wohl so sagen...

[redsky]

@RIDDICC

haha ok :). Vielen danke auf jeden Fall. Das was du gesagt hast passt auch mit der Musterlösung überein und ich denke ich habs verstanden, auch wenn ich's noch nicht so ganz toll formulieren kann.