Dijkstra Algorithmus?

CaPGeti

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;
}

mcr

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

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...

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

CaPGeti

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

Wie könnt ich die Zeile Umschreiben:

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

???

ich tippe auf:

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

CaPGeti

FALSCH ^^

der Lehrer hat gesagt:

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

Endlich kann ich mein wcIII clon weitermachen ^^

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

CaPGeti

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....

mcr

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

CaPGeti

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??

Bashar

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.

CaPGeti

ach vergisst es....

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

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