4. Dijkstra Algorithmus?

Dijkstra Algorithmus?

  • C

    Hallo..
    Ich wollte mal fragen wie der oben genannte Algorithmus funktioniert...
    Ich hab zwar schon in Wikipedia nachgeschaut, aber ich hab das ni kapiert...=(
    Außerdem hab ich auch schon ein sehr gutes Beispiel in QuickBasic, aber leider unkommentiert... Kann mir jemand weiterhelfen...

    0
  • ?

    Es macht wohl keinen Sinn, dir hier etwas zu beschreiben, was du im Internet hundertmal finden kannst. Irgendeine Erklärung wird für dich schon verständlich sein.

    0
  • C

    Hier hab ich den Algorithmus mal in QuickBasic...
    Kann ihn jemand in C schreiben... ich krieg das ni hin...

    DECLARE SUB showground ()
DECLARE SUB showpix (p AS INTEGER, Z AS ANY)

CONST dy = 23
CONST anz = 1816
CONST hinder = 1000

DIM SHARED qsuche(0 TO anz) AS INTEGER

DIM SHARED qdist(0 TO anz) AS INTEGER

DIM SHARED qvor(0 TO anz) AS INTEGER

DIM SHARED h(0 TO anz) AS INTEGER

DO

FOR i% = 0 TO anz
qsuche(i%) = 0
qdist(i%) = 0
qvor(i%) = 0
h(i%) = 0
NEXT
RANDOMIZE TIMER
FOR i% = 1 TO hinder
h(RND * (anz - 1) + 1) = 1
NEXT

FOR i% = 0 TO anz
IF i% MOD dy = 0 THEN h(i%) = 1
IF i% MOD dy = dy - 1 THEN h(i%) = 1
NEXT
Start% = RND * (anz - 1) + 1
Ziel% = RND * (anz - 1) + 1
h(Start%) = 0
h(Ziel%) = 0
DIM ri(8) AS INTEGER
DIM rd(8) AS INTEGER
ri(1) = -1
ri(2) = 1
ri(3) = -dy
ri(4) = dy
ri(5) = -1 - dy
ri(6) = 1 - dy
ri(7) = 1 + dy
ri(8) = -1 + dy

rd(1) = 3
rd(2) = 3
rd(3) = 3
rd(4) = 3
rd(5) = 4
rd(6) = 4
rd(7) = 4
rd(8) = 4
FOR i% = 0 TO anz
qdist(i%) = 32000
qvor(i%) = -1
IF h(i%) = 0 THEN qsuche(i%) = 1
NEXT
COLOR 4
showpix Start%, "S"
showpix Ziel%, "Z"
COLOR 7
showground

ti! = TIMER

qsuche(Ziel%) = 0
qdist(Start%) = 0
nichtleer% = 0
DO UNTIL nichtleer%
kdist% = 32000
k% = -1
FOR i% = 0 TO anz
IF qsuche(i%) <> 0 THEN
IF kdist% > qdist(i%) THEN
kdist% = qdist(i%)
k% = i%
END IF
END IF
NEXT
IF k% = -1 THEN
EXIT DO
END IF
qsuche(k%) = 0
FOR i% = 1 TO 8
v% = k% + ri(i%)
IF v% <= anz AND v% >= 0 THEN
IF h(v%) = 0 THEN
IF qdist(v%) > qdist(k%) + rd(i%) THEN
qdist(v%) = qdist(k%) + rd(i%)
qvor(v%) = k%
IF v% = Ziel% THEN EXIT DO
END IF
END IF
END IF
NEXT
nichtleer% = 1
FOR i% = 0 TO anz
IF qsuche(i%) <> 0 THEN nichtleer% = 0
NEXT
LOOP
COLOR 2
c% = Ziel%
DO
c% = qvor(c%)

IF c% = -1 THEN
PRINT "kein Weg"
EXIT DO
END IF
IF c% = Start% THEN EXIT DO
showpix c%, "*"

LOOP

ti2! = TIMER
LOCATE 1, 1
PRINT ti2! - ti!

SLEEP 3
CLS
LOOP UNTIL INKEY$ <> ""

SUB showground
FOR i% = 0 TO anz
IF h(i%) = 1 THEN showpix i%, "H"
NEXT
END SUB

SUB showpix (p AS INTEGER, Z AS STRING)
y% = p MOD dy + 1
x% = p \ dy + 1
LOCATE y%, x%
PRINT Z
END SUB

    ich hab zwar auch eine locate funktion, aber trotzdem..

    int locate(a,b){
    HANDLE stdOut = GetStdHandle(STD_OUTPUT_HANDLE);
    COORD xy;
    xy.Y = a;
    xy.X = b;
    SetConsoleCursorPosition(stdOut,xy);
    return 0;
}
    0
  • M

    Schau dir das mal an (keine 2 Minuten gegooglet, hättest du auch
    drauf kommen können)
    http://computer.howstuffworks.com/routing-algorithm3.htm

    Ich gebe zu, der Sourcecode sieht häßlich aus, aber vielleicht gibt
    dir das eine Idee, wie man den Implementieren kann.

    Aber, zuerst solltest du verstehen, wie der Algorithmus funktioniert,
    bevor du eine Implementierung versuchst zu verstehen.

    Gruß mcr

    0
  • ?

    kennst du die BASIC- und die C-syntax? die unterschiede sind nicht so gross:

    BASIC                          C
------------------------------------------
CONST a=6                     #define a 6
DIM a (0 TO anz) AS INTEGER   int a[anz];
FOR i% = 0 to anz             int i; for (i=0; i<=anz; i++)
ri(12) = -1                   r[12] = -1
RANDOMIZE TIMER               srand(time(0))
SUB showground                void showground(void)
y% = p MOD dy + 1             int y = p%(dy+1);

    usw...
    🙂

    0
  • ?

    in der letzten zeile^^ müssen die klammern wech.
    🙂

    0
  • C

    Hallo...ich hab grad ein Problem beim Umschreiben...

    Wie könnt ich die Zeile Umschreiben:

    h(RND * (anz - 1) + 1) = 1

    ???

    0
  • ?

    ich tippe auf:

    h[rand() * (anz - 1) + 1] = 1;

    🙂

    0
  • C

    FALSCH ^^

    der Lehrer hat gesagt:

    h[rand() % (anz - 1) + 1] = 1;

    Endlich kann ich mein wcIII clon weitermachen ^^

    0
  • ?

    '*' heisst auch in BASIC 'multipliziere' und nicht 'berechne den rest' wie '%'.
    🙂

    0
  • C

    so funktionierts aber..^^
    Außerdem hab ich ihn jetzt, auch wenn das doof ist, da ich das erst in 1d umrechnen muss und dann wieder in 2d... Oder hat jemand den algorithmus für 2d? glaub kaum ^^
    Danke für die Hilfen....

    0
  • M

    CaPGeti schrieb:

    so funktionierts aber..^^
    Außerdem hab ich ihn jetzt, auch wenn das doof ist, da ich das erst in 1d umrechnen muss und dann wieder in 2d... Oder hat jemand den algorithmus für 2d? glaub kaum ^^
    Danke für die Hilfen....

    Ich habe kaum eine Ahnung, was du mit 1d oder 2d meinst. Ich glaube aber,
    du meinst 1- oder 2-dimensional.

    Du glaubst kaum, dass jemand den Algorithmus für 2 Dimensionale Probleme hat?!
    Da muss ich dich aber enttäuschen. Der Algorithmus ist für beliebige Graphen
    definiert. Hier kommt es nicht auf die "Dimension" an.

    Du solltest vielleicht doch einmal überlegen, ob du dir den Algorithmus mal
    komplett anschaust und versuchst ihn zu verstehen. Eigentlich ist der total
    simple. Es ist kein Problem, diesen zu implementieren.

    Hier noch einmal zwei Links (von der deutschen Wikipedia-Seite), wo sehr
    anschaulich der Algorithmus beschrieben ist:
    http://algo2.iti.uni-karlsruhe.de/singler/algorithmus-der-woche/Kuerzeste Wege.pdf (nimm die gesamte URL! der Link geht so nicht. K.A. warum)

    http://www.mcgods.de/fun/1904/node8.html

    Gruß mcr

    0
  • C

    mhh.... ich glaub ich versteht mich nicht....
    ich mein, man muss ja irgentwie die y und x Koordinate übergeben und neu berechnen lassen, damit das "männl" dann auf den Bildschirm langläuft...
    Jetzt hab ich das so, das ich die y und x koordinate übergebe, dann ich die zwei werte als eine dimension umrechne:

    iPosition= iY*80+1+iX;

    und dann bei der ausgabe wieder umrechne:

    y = iPosition / dy + 1;
x = iPosition % dy + 1;

    wisst ihr jetzt was ich mein??

    0
  • B

    CaPGeti schrieb:

    mhh.... ich glaub ich versteht mich nicht....
    ich mein, man muss ja irgentwie die y und x Koordinate übergeben und neu berechnen lassen, damit das "männl" dann auf den Bildschirm langläuft...

    Ich weiß jetzt nicht, was du für den Dijkstra-Algorithmus hältst, aber mit rumlaufenden Männchen hat das nichts zu tun. Der Dijkstra-Algorithmus findet in einem gewichteten Graphen die kürzesten Pfade von einem Startknoten zu allen anderen Knoten.

    0
  • C

    ach vergisst es....

    Startknoten = aktuelle position
    Zielknoten = dort wo es sich befinden soll

    aber egal...muss ich mal woanders gucken....

    0
Anmelden zum Antworten