=?windows-1252?Q?Re=3A_=5Bpersonal_kdb=2B=5D_dijkstra=92s_algorithm_with_Q_pr?=

Community Support
1

try starting with a matrix that represents your diagram like:
/ ?A ?B ?C ?D ?E ?F ?G
(( 0 ?1 0N 0N ?1 ?4 20); /A

?( 1 ?0 ?5 0N 0N ?2 0N); /B

?(0N ?5 ?0 0N ?6 ?2 0N); /C

?(0N 0N 0N ?0 ?1 ?2 ?5); /D

?(0N 0N ?6 ?1 ?0 0N 0N); /E?

?( 4 ?2 ?5 ?2 0N ?0 0N); /F
?(20 0N 0N ?5 0N 0N ?0); /G

)


transform the matrix repeatedly according to the theory you are using. ?maybe use /(over) or (iterate)

2

Correct, you need a way to represent graphs in q.<o:p></o:p>

Take a look at http://archive.vector.org.uk/art10500340. This will help you get started.<o:p></o:p>

<o:p> </o:p>

Kim<o:p></o:p>

<o:p> </o:p>

Von: personal-kdbplus@googlegroups.com [mailto:personal-kdbplus@googlegroups.com] Im Auftrag von Jack Andrews
Gesendet: Montag, 8. April 2013 10:52
An: Kdb+ Personal Developers
Betreff: Re: [personal kdb+] dijkstra’s algorithm with Q problem<o:p></o:p>

<o:p> </o:p>

try starting with a matrix that represents your diagram like:<o:p></o:p>

/  A  B  C  D  E  F  G<o:p></o:p>

(( 0  1 0N 0N  1  4 20); /A<o:p></o:p>

 ( 1  0  5 0N 0N  2 0N); /B<o:p></o:p>

 (0N  5  0 0N  6  2 0N); /C<o:p></o:p>

 (0N 0N 0N  0  1  2  5); /D<o:p></o:p>

 (0N 0N  6  1  0 0N 0N); /E <o:p></o:p>

 ( 4  2  5  2 0N  0 0N); /F
 (20 0N 0N  5 0N 0N  0); /G<o:p></o:p>

)<o:p></o:p>

<o:p> </o:p>

transform the matrix repeatedly according to the theory you are using.  maybe use /(over) or (iterate)<o:p></o:p>

–
Submitted via Google Groups

3

Here’s a first attempt. Not optimized for performance but should give some ideas:

//based on the example here:?http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html

//define the nodes and their connections/values

nodes.O:AB`C!2 5 4

nodes.A:OBDF!2 2 7 12

nodes.B:OCED`A!5 1 3 4 2

nodes.C:OB`E!4 1 4

nodes.D:BETA!4 1 5 7

nodes.E:CBDT!4 3 1 7

nodes.F:AT!12 3

nodes.T:ED`F!7 5 3

//function to calc shortest path

dijkstra:{[start;end]

?//starting point

?solved:enlist[start]!enlist 0;

?solved,:![;enlist v] enlist k:d?v:min d:solved[start]+nodes[start];

?path:enlist[k]!enlist start;

?//iterate

?while[k<>end;

solved,:![;enlist b] enlist k:?[;b] d v:a?b:min a:min each d:solved+key[solved]_/:nodes key solved;

path[k]:v];

?//resolve the path after iteration complete

?(last solved;reverse except[;`] path[end])

?}

q)dijkstra[O;T]

13

OABD`T

So the shortest route from O to T has distance 13 via AB`D

This solution doesn’t find alternative routes of same minimal length and possibly doesn’t cover edge cases.

4

Were you trying to paste it into a running q session? The running q session does not support multi-line input like that.

You should put the function in a q script and have q load in the script

Note that the final “}” must be indented

5

http://code.kx.com/wiki/Startingkdbplus/qlanguage#2.9_Scripts

A script can contain multi-line definitions. Any line that is indented is assumed to be a continuation of the previous line. 

I think you have not indented each continued line for that function.