Hi
Anyone coded dijkstras algo in asm?
First you setup distances to infinite, examples show define some high integer as infinite
But if i write a fpu version using REAL10, for example distances = between stars, I could use fpu own infinity + when comparing and not be capped to use max dword as infinity?
+infinity =7F800000h
-infinity =FF800000h
Should I use some random create grid proc, but with fixed seed = creates same grid every time?
Beginning coding
; dijkstras algo
Cost Db 8*5 dup (infinity)
Align 8 ; can use [reg*8 ] indirect addressing for one dimension of array
G db 0,1,0,3,10
Align 8
Db 1,0,5,0,0
Align 8
Db 0,5,0,2,1
Align 8
Db 3,0,2,0,6
Align 8
Db 10,0,1,6,0
Local n,u
Mov n,5
Mov u,0
Invoke dijkstra(G,n,u);
return 0;
dijkstra proc,(G,n,u);
Mov edx,0
Lea esi,G
L1:Mov ecx,0
L2: Mov eax,[addr G+edx*8+ecx]
If eax==0
Mov [addr cost+edx *8+ecx ],infinity
Else mov [addr cost+edx*8+Ecx],eax
Endif
Inc ecx
Cmp ecx,n
Jne l2
Inc edx
Cmp edx, n
Jne l1
Ret
dijkstra endp
maybe better to start with GDI drawing street network,by drawing streets up to 4 directions from nodes,easier understood and easier to watch it find the way if it works or bug causes it to take wrong route???
route taken = draw in different street color
Sorry, no answer (as usual, I have trouble even understanding just what you're after here), but for those of you like me who have no idea what Dijkstra's algorithm is, here's a really good explanation (https://www.freecodecamp.org/news/dijkstras-shortest-path-algorithm-visual-introduction/). (I really like it when someone clearly and elegantly explains something.)
Other source: https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
Apparently was a simple code and an easy translation :biggrin: ( :eusa_naughty: )
In 64 bit is largeaddressaware:no to make that more easy. And 32/64 differ because vasily conditionals, then only Masm SDK requiered:
dijkstra proc src:xword
local i : xword, count : xword, u : xword, v : xword
; Function that implements Dijkstra's single source
; shortest path algorithm for a graph represented using
; adjacency matrix representation
; Initialize all distances as INFINITE and stpSet[]
; as false
ForLpD i, 0, sgraph
mov xcx, infinite
mov dist[xax*@WordSize], xcx
mov sptSet[xax*@WordSize], 0
Next i
; Distance of source vertex from itself is always 0
mov xax, src
mov dist[xax*@WordSize], 0
; Find shortest path for all vertices
ForLpD count, 0, sgraph-1
; Pick the minimum distance vertex from the set
; of vertices not yet processed. u is always
; equal to src in first iteration.
call minDistance
mov u, xax
; Mark the picked vertex as processed
mov sptSet[xax*@WordSize], 1
; Update dist value of the adjacent vertices of
; the picked vertex.
ForLpD v, 0, sgraph, xdx
; Update dist[v] only if is not in sptSet,
; there is an edge from u to v, and total
; weight of path from src to v through u is
; smaller than current value of dist[v]
.if sptSet[xdx*@WordSize] == 0
matrix u, v, sgraph
mov xcx, graph[xax*@WordSize]
.if xcx != 0
mov xdx, u
mov xax, dist[xdx*@WordSize]
.if xax != infinite
add xax, xcx
mov xdx, v
.if xax < dist[xdx*@WordSize]
mov dist[xdx*@WordSize], xax
.endif
.endif
.endif
.endif
Next v
Next count
; print the constructed distance array
invoke printSolution
ret
dijkstra endp
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
Pardon my ignorance here... xax, xcx, xword??? What type of sorcery conjured this up? :biggrin:
A new CPU architecture? Macros? Other? :tongue:
I haven't downloaded it yet, HSE.. But now I'm curious... :biggrin:
Seems a little advanced... But a very interesting topic. Maybe this would be more suitable in the Workshop? Or even the Laboratory (to make it better, faster, etc)...
Later...
Quotexax, xcx, xword
Ah, okay I see. Macros... You made the program conditionally usable with either 32 bit or 64. :thumbsup:
The batch file may need correction.
Quote\masm32\bin64\ml64.exe /c %appname%.asm
\masm32\bin64\polink.exe /SUBSYSTEM:CONSOLE /MACHINE:X64 /ENTRY:entry_point /nologo /LARGEADDRESSAWARE:NO %appname%.obj
Originally hutch had everyone incorporate masm64 within the masm32 directory.
The latest version of the SDK is meant to be installed apart from the masm32 SDK... in the root of the drive....
I have corrected the batch files for my installation of the masm64 SDK...
Quote\masm64\bin64\ml64.exe /c %appname%.asm
\masm64\bin64\link.exe /SUBSYSTEM:CONSOLE /MACHINE:X64 /ENTRY:entry_point /nologo /LARGEADDRESSAWARE:NO %appname%.obj
Nice work there HSE. :thumbsup:
With some modifications perhaps, should do what Magnus needs. :smiley:
thanks hector :thumbsup:
; Initialize all distances as INFINITE and stpSet[]
; as falseI already changed to already db 5*8 dup (infinite)
but I still believe in a graphics version better than print data
What HSE posted could be a good starting point???
Quote from: zedd151 on October 12, 2023, 02:53:31 AMYou made the program conditionally usable with either 32 bit or 64. :thumbsup:
That is the point :thumbsup: Biterider refer to this like "Neutral Bitness", sometimes you see the concept like "x96".
This example is partially x96 for simplicity reasons, and don't need any additional macro.
To be complete Neutral Bitness for ML/ML64 must use some macros presents in SmplMath, not the idea here.
Quote from: daydreamer on October 12, 2023, 04:18:55 AMbut I still believe in a graphics version better than print data
You are the expert in graphics :thumbsup:
Quote from: HSE on October 12, 2023, 06:52:47 AMQuote from: zedd151 on October 12, 2023, 02:53:31 AMYou made the program conditionally usable with either 32 bit or 64. :thumbsup:
That is the point :thumbsup: Biterider refer to this like "Neutral Bitness", sometimes you see the concept like "x96".
Same as Dual 64- and 32-bit Assembly (https://masm32.com/board/index.php?topic=9266.0)
Quote from: jj2007 on October 12, 2023, 07:17:59 AMSame as Dual 64- and 32-bit Assembly
Neutral Bitness is about a few equates and a couple of very simple macros.
For a system, like your "Dual", is far better ObjAsm package complemented with SmplMath (and all code is available) :skrewy:
Quote from: HSE on October 12, 2023, 09:42:01 AMNeutral Bitness is about a few equates and a couple of very simple macros.
You are the expert :thumbsup: