Jump to content

Dijkstra algorithm.


Recommended Posts

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

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
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...