March 10, 2005 at 8:18 am
Does anyone know if an implimentation of the dijkstra shortest path or similar algoritm is available for SQL server.
I've done some googling and havn't found anything as yet but thought that you guys may know where a solution could be found.
If not I guess I'll have to (attempt to) do it myself (although don't hold your breath).
Cheers
Stephen
(P.S. Nope I'm not still at uni. [although I wish I was] and this is not my homework [and I'm glad it's not]).
March 10, 2005 at 10:10 am
Hi Stephen,
Just out of interest - what are you trying to solve with this?
Can you give us some examples of data etc?
Have fun
Steve
We need men who can dream of things that never were.
March 10, 2005 at 12:34 pm
Based on experience, I suggest you do NOT do this in SQL !!!
Recommend that you use a a programiing language (C++/C/Vb?) where you should load the data into in-memory arrays/lists/whatever and then perform the processing.
References:
Joe Celko's column title "Happier marriages through math" with a sub-title of "Procedural code can be useful for computation-intensive queries." at http://www.dbmsmag.com/9808d06.html
See also "Using CLR Integration in SQL Server 2005" at http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnsql90/html/sqlclrguidance.asp
You could post to microsoft.public.sqlserver.programming where there are a couple of Math Ph.D.s lurking that love these type of problems.
SQL = Scarcely Qualifies as a Language
March 14, 2005 at 3:48 am
In Answer to steve:
Routing using UK OS (eithier OSCAR or Intergrated Transport Layer) road data.
As to samples I would probably have to roll my own so I'm not suire what format it would be in yet.
In Answer to Carl:
It "felt" from my intial reading thata DB should be suited to the problem in additon to better load balancing (also our DB server is a lot more powerful than our Web/GIS server 🙂
Stephen
March 15, 2005 at 11:38 am
G'day all,
Solutions to dijkstra's algorithm and related processes are often seen in the DB as hierarchy traversal routines. DBs are actually quite good at solving the problem, as it is trivial to add a weight (or cost) to a specific parent-child node in a hierarchy or a network. Given this fundamental ability, we can then apply a set based query that will use the minimal traversal (minimum number of nodes), a minimal cost, or other min/max solution to derive the shortest path between any two nodes stored in the DB.
I developed a solution a year ago that used a variation on Dijkstra's algorithm in the utility space around managing the energy grid.
It is worthy of note that once we figure out how to apply Dijkstra's algorithm to a problem space using a DB; there is frequently a more optimum solution using set based logic.
Feel free to ping me directly for more specifics.
hth
Wayne
March 15, 2005 at 11:44 am
Another note - Kimball has done some fair amount of work in the data warehouse space and discusses the use of "bridge tables" to assist in the fast query and retrieval of hierarchical data. In essence, a bridge table contains a source/target row for every possible combination in a directed graph, or more commonly, a hierarchy. Then simply add a weight or cost to each row in the bridge table. A directed graph is important as cycles are a bit problematic in a DB. This allows the use of a single select to gather all paths, order by associated weight, resulting in a trivial query to retreive the solution to any particular traversal problem.
In addition to traffic management, this problem occurs frequently in logistics and shipment management systems, where the cost may be time, financial, security, or any combination of these factors. The bridge table allows the use of multiple types of weights while storing that actual network once.
hth
Wayne
March 15, 2005 at 11:43 pm
Hi Stephen,
I agree with Carl, you should do the algorithm in C/C++ or Java rather than TSQL. I have worked on several very large genomic databases that require much mathematical manipulation - neural nets, genetic algos, segmentation etc, and I have found that ( unsurprisedly ) TSQL is just too slow. TSQL is designed to store and get data, and it does that very well.
March 16, 2005 at 7:30 am
All,
I would concur with Carl and Bob that if you intend to implement any of the procedural, computationally intensive algorithms directly then you will have an easier go of it in a procedural language.
Having said that, the reason that a DB solution *may* make sense is that the networks involved in this particular problem domain changes relatively infrequently. As such, it is technically feasible to precompute and store the routes, associated weights, and other attributes. Once stored, the DB is well suited to providing simple, rapid retrieval of the least expensive route.
If the routes changed frequently (multiple routes changing in near real time), then I would tend to recommend the procedural solution more strongly. I suspect that you will be loading the data store of routes in a batch mode which lends itself quite well to a precompute-and store algorithm.
Can you provide any more details regarding the problem domain? Frequency of update? Requirements for immediate route updates and so on?
Viewing 8 posts - 1 through 7 (of 7 total)
You must be logged in to reply to this topic. Login to reply