Jump to content
Sign in to follow this  
jokke

Dijkstra algorithm.

Recommended Posts

jokke

Hiya, im close to finish my dijkstra algorithm but are having some problems im unable to revese the search where end = 0 and start = 16

I hope i have done everything right please have a look:

CODE
;-----------------------------------------------------

; Djikstra algorithm.

; Find the shortest route to goal.

;

; Example, 18 nodes mapped out, make a logic decision on what's the shortest route.

;-----------------------------------------------------

;Visual map mapped inn a graph.

;1=mapped

;S=Start

;E=end

; X

;6| | | |S|1| |

;5| | |1| |1| |

;4| | |1|1| |1|

;3| |1| | | |1|

;2| |1|1|1|1| |1

;1|1| | | |E| |1

; +-------------Y

;# 1|2|3|4|5|6|7

;From reading the graph one can see that taking this route is the shortest (counting from S node to E node):

;0 = x6,y4

;1 = x5,y5

;2 = x4,y6

;3 = x3,y6

;4 = x2,y5

;5 = x1,y5

#include <array.au3>

Dim $node[17][3] ;[#][x,y,tested]

$node[0][0] = 6

$node[0][1] = 4

$node[1][0] = 6

$node[1][1] = 5

$node[2][0] = 5

$node[2][1] = 3

$node[3][0] = 5

$node[3][1] = 5

$node[4][0] = 4

$node[4][1] = 3

$node[5][0] = 4

$node[5][1] = 4

$node[6][0] = 4

$node[6][1] = 6

$node[7][0] = 3

$node[7][1] = 2

$node[8][0] = 3

$node[8][1] = 6

$node[9][0] = 2

$node[9][1] = 2

$node[10][0] = 2

$node[10][1] = 3

$node[11][0] = 2

$node[11][1] = 4

$node[12][0] = 2

$node[12][1] = 5

$node[13][0] = 2

$node[13][1] = 7

$node[14][0] = 1

$node[14][1] = 1

$node[15][0] = 1

$node[15][1] = 5

$node[16][0] = 1

$node[16][1] = 7

Dim $cost = "UNKNOWN"

Global $from[2]

Global $to[2]

$max = 1.5

$start = 0

$end = 15

Dim $tmp_path,$tmp_cost

Dim $path_array,$path_cost = "NONE"

$timer = TimerInit()

For $u = 0 To UBound($node)-1

$tmp_path = generate_path($start,$end,$u)

If UBound($tmp_path) > 0 Then

$tmp_cost = check_cost($tmp_path)

If $path_cost = "NONE" Or $tmp_cost < $path_cost Then

$path_array = $tmp_path

$path_cost = $tmp_cost

EndIf

EndIf

Next

ConsoleWrite("Timer: " &TimerDiff($timer)& " ms." & @CRLF)

ConsoleWrite("Short route lenght: " & $path_cost & " Nodes: " & UBound($path_array) & @CRLF)

_ArrayDisplay($path_array,"path")

Func check_cost($path)

Local $a[2],$b[2]

$cost = 0

For $x = 1 To UBound($path) -1

$a[0] = $node[$path[$x-1]][0]

$a[1] = $node[$path[$x-1]][1]

$b[0] = $node[$path[$x]][0]

$b[1] = $node[$path[$x]][1]

$cost += distance($a,$muttley

Next

Return $cost

EndFunc

Func generate_path($f, $t, $blacklisted)

Local $path[1],$lenght = 1,$current = $f

$path[0] = $f

For $x = 0 To UBound($node) -1

$from[0] = $node[$current][0]

$from[1] = $node[$current][1]

$to[0] = $node[$x][0]

$to[1] = $node[$x][1]

If distance($from,$to) < $max And distance($from,$to) >= 1 And $x <> $blacklisted And $node[$x][2] <> 1 Then

ReDim $path[$lenght+1]

$current = $x

$path[$lenght] = $current

$lenght +=1

EndIf

If $current = $t Then

Return $path

EndIf

Next

$node[$current][2] = 1

EndFunc

Func distance($from,$to)

Local $dis

$dis = Sqrt(($from[0] - $to[0]) ^ 2+ ($from[1] - $to[1]) ^ 2)

Return Round($dis,2)

EndFunc


UDF:Crypter a file encrypt / decrypt tool with no need to remember a password again. Based on Caesar cipher using entire ASCII Table.Script's: PixelSearch Helper, quick and simple way to create a PixelSeach.Chatserver - simplified, not so complicated multi-socket server.AutoIT - Firewall, simple example on howto create a firewall with AutoIt.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×