Bellman - Verfahren

hänge gerade am Bellmann-Verfahren.

Kann mir jemand mal bitte erklären wie ich zur Lösung der Aufgabe B0303 komme.

Bellman-Verfahren - B303

Gruß!
Sigi

Man muß nur der Reihe nach die kürzesten Wege finden:

Immer angegeben in J di qi <Route>
Also Knoten zu dem die Reise geht / Kosten / Vorgängerknoten/ Gesamtroute
Für Knoten A noch ganz simpel:

A 0 A <A>

Knoten B,C,D, E sind nur von A erreichbar:
B 2 A <AB>
C 1 A <AC>
D 2 A <AD>

Knoten E ist nur von C erreichbar, die günstigste Enftfernung ist damit die nach C plus der Kosten nach E
E 3 C <ACE>

So, bei Knoten F gibt es zwei Möglichkeiten, entweder über Knoten B Kosten 2 + 2, oder Knoten D Kosten 2+1, wir wählen den günstigeren Weg:
F 3 D <ADF>

G hat vier Vorgängerknoten, auch hier wieder Vergleich der Gesamtkosten C: 1+2 vs. D 2+2 vs. E 3+3 vs. F 3+2 --> wir fahren über C
G 3 C <ACG>

usw usf. bis man am Ende der Tour angekommen ist

danke - also ist das ganze rhythmisch hinschauen nach Rödder 🙂 - so lange ich es ohne EDV mache.

Ich suche Knoten für Knoten nach der kürzesten Verbindung welche sich ergibt und summiere die Kosten/Strecken (dj).

Was ist denn in seiner Lösung das qj?

Gruß
Sigi

qj ist der Vorgängerknoten, ich bin ein Mensch und kann durchaus das ABC durchnummerieren und weiß, daß nach A B folgt und dann C.
Rödder und sein Algorithmus nicht, daher benennt der erstmal A=1 B=2 C=3 usw.