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

## Create an account

Register a new account