Dijkstras algo with fpu?

[daydreamer]

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

Code Select Expand

; 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
 



[daydreamer]

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

[NoCforMe]

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. (I really like it when someone clearly and elegantly explains something.)

[HSE]

Other source:  https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

Apparently was a simple code and an easy translation  (  )

In 64 bit is largeaddressaware:no to make that more easy. And 32/64 differ because vasily conditionals, then only Masm SDK requiered:

Code Select Expand

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
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤


[zedd]

Pardon my ignorance here... xax, xcx, xword??? What type of sorcery conjured this up? 
A  new CPU architecture? Macros? Other?

I haven't downloaded it yet, HSE.. But now I'm curious... 

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

[zedd]

Later...

xax, xcx, xword

Ah, okay I see. Macros... You made the program conditionally usable with either 32 bit or 64. 


The batch file may need correction.

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

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

With some modifications perhaps, should do what Magnus needs. 

[daydreamer]

thanks hector 

Code Select Expand

; 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

[zedd]

What HSE posted could be a good starting point???

[HSE]

You made the program conditionally usable with either 32 bit or 64. 

That is the point  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.

but I still believe in a graphics version better than print data

You are the expert in graphics 

[jj2007]

You made the program conditionally usable with either 32 bit or 64. 

That is the point  Biterider refer to this like "Neutral Bitness", sometimes you see the concept like "x96".

Same as Dual 64- and 32-bit Assembly

[HSE]

Same 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)   

[jj2007]

Neutral Bitness is about a few equates and a couple of very simple macros.

You are the expert