jokke Posted July 13, 2008 Share Posted July 13, 2008 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. Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now