Prim und Bellman

ChristianeH schrieb:

So nachdem der bereich hier jetzt auch "offiziell" eröffnet wurde, frag ich auch schnell.
Und zwar hab ich Probleme gerae mit Prim (umgeh ich immer und nehm Kruskal*G*, aber blicken sollte ich ihn trotzdem).
Außerdem hänge ich über Bellman.
1. Wie kommt man auf das a=2 in der Beispielsaufgabe 3.2? Ist das nur ein Beispiel oder zwingend?
2. der ganze Algorithmus ist für mich unveständlich dargestellt. Durch irgendwie ausprobieren bin ich auf die Lösung gekommen aber nie so wie es da steht. Wie kann man das denn mal in normalen Worten (am Algorithmus entlang) erklären?

Zum Vergrößern anklicken....

Zu 1: Als Startknoten kannst Du jeden beliebigen waehlen. Im Beispiel ist es der Knoten Nr 2. Anders als Ford berechnet er jedoch nur die Distanzen zwsichen Startknoten und den anderen.

Zu 2: Du startest in a. Zuerst berechnest Du alle Distanzen von diesem Knoten zu seinen Nachfolgern. Dann denkst Du Dir diese Kanten vom Startknoten zu seinen Nachfolgern weg und nimmst den Knoten, der keine Eingangsknoten mehr hat. Fuer diesen machst Du das gleiche wie eben fuer den Startknoten. Wenn keine Knoten mehr zur Verfuegung stehen, bricht der Algorithmus ab.

Was verstehst Du im Prim nicht? Unterschied zum Kruskal ist eigentlich nur, dass Du am bestehenden Baum weiterbaust. Kruskal fuehrt im Extremfall erst am Schluss alle Waelder zu einem Baum zusammen.