cancel
Showing results for 
Search instead for 
Did you mean: 

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

effbiae
New Contributor
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)
4 REPLIES 4

kuentang
New Contributor

Correct, you need a way to represent graphs in q.

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

 

Kim

 

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

 

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)

--
You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbplus+unsubscribe@googlegroups.com.
To post to this group, send email to personal-kdbplus@googlegroups.com.
Visit this group at http://groups.google.com/group/personal-kdbplus?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

TerryLynch
New Contributor II
Here's a first attempt. Not optimized for performance but should give some ideas:


//define the nodes and their connections/values

nodes.O:`A`B`C!2 5 4
nodes.A:`O`B`D`F!2 2 7 12
nodes.B:`O`C`E`D`A!5 1 3 4 2
nodes.C:`O`B`E!4 1 4
nodes.D:`B`E`T`A!4 1 5 7
nodes.E:`C`B`D`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`A`B`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.




TerryLynch
New Contributor II

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

charlie
New Contributor II
New Contributor II

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.