5.6

[*_konkreeet_*]

Dijkstra's Algorithm

shortest_paths( Graph g, Node s )
initialise_single_source( g, s )
S := { 0 } /* Make S empty */
Q := Vertices( g ) /* Put the vertices in a PQ */
while not Empty(Q)
u := ExtractCheapest( Q );
AddNode( S, u ); /* Add u to S */
for each vertex v in Adjacent( u )
relax( u, v, w )

initialise_single_source( Graph g, Node s )
for each vertex v in Vertices( g )
g.d[v] := infinity
g.pi[v] := nil
g.d[s] := 0;

The relaxation procedure checks whether the current best estimate of the shortest distance to v (d[v]) can be improved by going through u (i.e. by making u the predecessor of v):

relax( Node u, Node v, double w[][] )
if d[v] > d[u] + w[u,v] then
d[v] := d[u] + w[u,v]
pi[v] := u

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html (http://ciips.ee.uwa.edu.au/%7Emorris/Year2/PLDS210/dijkstra.html)

[_logonoff_]

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html (http://ciips.ee.uwa.edu.au/%7Emorris/Year2/PLDS210/dijkstra.html)

sehr empfehlenswert ist auch, sich die dortige animation der vorgehensweise des algorithmus anzusehen - da versteht man den das ding gleich viel schneller :)


achja, und wer nicht so wirklich weiß, was die manhattan-metrik tut:
http://de.wikipedia.org/wiki/Normierter_Raum#p-Normen

das ergibt dann als gewichte für die kanten (sofern ich mich nicht vertan hab):

[edit] hab mich natürlich vertan, weil ich die manhattan metrik nicht ganz richtig verstanden hatte

[Septic.exe]

Ich hab andere Gewichte gefunden:

(A, B) = 10, (B, C) = 3, (B, D) = 5, (D, E) = 4, (E, F) = 7, (E, G) = 4, (G, H) = 3, (A, G) = 5, (H, J) = 4, (I, J) = 5, (J, K) = 4, (K, L) = 3, (L, M) = 3, (D, K) = 7;

[*_konkreeet_*]

habts ihr auch das selbe koordinatensystem?

ich hab zb. F(0/10) und C(1/0)

[Septic.exe]

Das ist in dem Fall egal ... glaub ich.

Ich poste mal meine Lösung, ausgehend vom Punkt A (Funktionsweise des Algorithmus von Dijkstra):

- Startpunkt A und nimm A (K=0) da geringsten Wert (setze rot)
- suche Nachbarn G und B, die noch nicht rot sind (setze grün)
- update Knoten G (K=5)und B (K=10)
- nimm Knoten mit geringstem Wert G (K=5) (setze rot)
- suche Nachbarn E und H, die noch nicht rot sind (setze grün)
- update Knoten E (K=9) und H (K=8)
- nimm Knoten mit geringstem Wert H (K=8) (setze rot)
- suche Nachbarn J, die noch nicht rot sind (setze grün)
- update Knoten J (K=12)
- nimm Knoten mit geringstem Wert E (K=9) (setze rot)
- suche Nachbarn D und F, die noch nicht rot sind (setze grün)
- update Knoten D (K=13) und F (K=16)
- nimm Knoten mit geringstem Wert B (K=10) (setze rot)
- suche Nachbarn C, die noch nicht rot sind (setze grün)
- updaten Knoten C (K=13)
- nimm Knoten mit geringstem Wert J (K=12) (setze rot)
- suche Nachbarn I und K, die noch nicht rot sind (setze grün)
- update Knoten I (K=17) und K (K=16)
- nimm Knoten mit geringstem Wert D (K=13) (setze rot)
- suche Nachbarn B und K, die noch nicht rot sind (setze grün)
- update Knoten B (K=10)
- nimm Knoten mit geringstem Wert B (K=10) (setze rot)
- suche Nachbarn C, die noch nicht rot sind (setze grün)
- update Knoten C (K=13)
- nimm Knoten mit geringstem Wert C (K=13) (setze rot)
- suche Nachbarn, die noch nicht rot sind (setze grün … in dem Fall gibt es keine Knoten)
- update keine Knoten
- nimm Knoten mit geringstem Wert F (K=16) (setze rot)
- suche Nachbarn, die noch nicht rot sind (setze grün … in dem Fall gibt es keine Knoten)
- update keine Knoten
- nimm Knoten mit geringstem Wert K (K=16) (setze rot)
- suche Nachbarn L, die noch nicht rot sind (setze grün)
- update Knoten L (K=19)
- nimm Knoten mit geringstem Wert I (K=17) (setze rot)
- suche Nachbarn, die noch nicht rot sind (setze grün … in dem Fall gibt es keine Knoten)
- update keine Knoten
- nimm Knoten mit geringstem Wert L (K=19) (setze rot)
- suche Nachbarn M, die noch nicht rot sind (setze grün)
- update Knoten M (K=22)
- nimm Knoten mit geringstem Wert M (K=22= (setze rot)
- finito

[mmp]

Das ist in dem Fall egal ... glaub ich.

Jo es ist sicher fix egal welche koordinatensystem man hat, da alles in abständen gemessen wird.

So werd mal meine ergebnisse posten, soweit ich gesehen hab, stimmen sie mit deinen überein.

A(0) B(10) C(13) D(13) E(9) F(16) G(5) H(8) I(17) J(12) K(16) L(19) M(22)

[*_konkreeet_*]

wie schaudn eigentlich euer pseudocode aus ?

ich hab:


shortest_paths(G,E) {

für alle Kanten (u,v) € E {
berechne Gewicht (u,v):= (u.x-v.x)+(u.y-v.y);
}
shortest_paths1(T,Q,s);
}

shortest_paths1(T,Q,s) {
markiert[s]=1;
T={s};
Q=V;

while Q != 0 {
u:= Knoten mit (s,u) € E && Gewicht(s,u) geringestes Gewicht aller (s,x) mit x € N(s)
if (markiert[s] != 1) {
T = T v {u};
für jeden Knoten w € N(u) {
shortest_paths1(T,Q,w);
}
}
}
}

is das ok ?

[johnDoe]

Pseudocode ist lt. Angabe doch gar nicht gefordert!?

[Septic.exe]

Jo ... nur der Algorithmus is gefordert ... zum Glück ... aber Pseudocode is ja auch Algorithmus ;).

[*_konkreeet_*]

*schwitz* hab scho fast glaubt, ich muss mich mit an socken erschießen ...
also, passt der jetzt? :engel:

[Tschebel]

hoi i glaub da oben drinne is a fehler
knoten b wurde 2mal genommen, darf das denn sein? theoretisch dürfte das einen kreis ergeben

[Septic.exe]

... leicht möglich, daß ich mich in dem Wirrwarr irgendwo vertan hab ... aber das Prinzip dürfte durch die Auflistung der einzelnen Schritte klar ersichtlich sein :) ... bin aber zu faul, das jetzt nochmals durchzurechnen ;).

[MrAngel]

Auch eine sher gute Seite auf Deutsch mit den einzelnen Schritten!

http://wwwmayr.informatik.tu-muenchen.de/skripten/ead_ws9899_html/node81.html

MFG MrAngel