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)
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
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:A
B`C!2 5 4
nodes.A:O
BD
F!2 2 7 12
nodes.B:O
CE
D`A!5 1 3 4 2
nodes.C:O
B`E!4 1 4
nodes.D:B
ET
A!4 1 5 7
nodes.E:C
BD
T!4 3 1 7
nodes.F:A
T!12 3
nodes.T:E
D`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
O
AB
D`T
So the shortest route from O to
T has distance 13 via A
B`D
This solution doesn’t find alternative routes of same minimal length and possibly doesn’t cover edge cases.
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
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.