cancel
Showing results for
Did you mean:

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

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
New Contributor

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

Kim

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.

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.

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

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.