Author 
Topic 
Bostaka 
Posted  2010.07.22 18:35:00  [ 1]
Edited by: Bostaka on 22/07/2010 18:37:13 Edited by: Bostaka on 22/07/2010 18:35:32 Heya,
I failed my degree in computer science so ...
Using the Tyrannis SQL datadump, what's the easiest way of finding the quickest route between two systems and the like? If someone could give me something to Google as a starting point that would be great! It's been 10 years since I touched this algorithm and I dont think it would have worked on a database anyway...
I'm prepared to get my hands dirty, in fact that's the idea, I can handle a bit of mysql/php but please bare in mind I failed miserably at the mathematical side of things and algorithms like this at the best of times so pls go easy on the terminology!!
Ty :)) 
Gar Karath Caldari 
Posted  2010.07.22 18:42:00  [ 2]
Edited by: Gar Karath on 22/07/2010 18:54:31 Originally by: Bostaka Edited by: Bostaka on 22/07/2010 18:37:13 Edited by: Bostaka on 22/07/2010 18:35:32 Heya,
I failed my degree in computer science so ...
Using the Tyrannis SQL datadump, what's the easiest way of finding the quickest route between two systems and the like? If someone could give me something to Google as a starting point that would be great! It's been 10 years since I touched this algorithm and I dont think it would have worked on a database anyway...
I'm prepared to get my hands dirty, in fact that's the idea, I can handle a bit of mysql/php but please bare in mind I failed miserably at the mathematical side of things and algorithms like this at the best of times so pls go easy on the terminology!!
Ty :))
There are several possibilities. The easiest one might be: Dijkstra's AlgorithmAnother option is the A star search algorithmWith a star you can use the system coordinates for the cost function. Have fun reading ;) Edit: Eve Forum Link Fail .. here are the links: http://en.wikipedia.org/wiki/Dijkstra's_algorithm http://en.wikipedia.org/wiki/A*_search_algorithm 
CCP Atropos

Posted  2010.07.22 19:47:00  [ 3]
This has come up a bunch of times before, so just put Dijkstra into the search box in the top right up there 
Flammard Caldari The New Era C0NVICTED 
Posted  2010.07.25 00:56:00  [ 4]
Edited by: Flammard on 25/07/2010 01:18:05 A simple breadth first search will find you the shortest hop count, if you want to start with something simple. It's easier to understand than Dijkstra's algorithm or A*.
If you want to take security status into account then you will need to use Dijkstra's algorithm, which is slightly more complex.
TBH I wouldn't bother with A*. It's a lot more complex than what is required.
About a year ago I slapped together a small C program that did a BFS search to find the shortest hop count between two systems as an exercise, but once I got it working I never really developed it further. If anyone wants it I can search for it and post it somewhere. 
Ambo I've Got Nothing

Posted  2010.07.25 07:12:00  [ 5]
Edited by: Ambo on 25/07/2010 07:35:53My final solution was to do some preprocessing of the data and then use Djikstra's algorithm: This MSSQL code creates two new tables, SolarSystemJumps and SolarSystemDistances. It takes a few seconds to executes and only needs to be run once (and then each time the map is updated from the datadump.) Quote:  Thanks go to 'Jethro Jechonias' for the original version of this code.
/* Create tables for distance calculation Drop and recreate tables if they already exist [dbo].[SolarSystemJumps] [dbo].[SolarSystemDistances]*/ if exists (select * from dbo.sysobjects where id = object_id(N'[dbo].[SolarSystemJumps]') and OBJECTPROPERTY(id, N'IsUserTable') = 1) drop table [dbo].[SolarSystemJumps] CREATE TABLE [dbo].[SolarSystemJumps] ( [FromSolarSystemID] [int] NOT NULL , [ToSolarSystemID] [int] NOT NULL , CONSTRAINT [PK_SolarSystemJumps] PRIMARY KEY CLUSTERED ( [FromSolarSystemID], [ToSolarSystemID] ) ) if exists (select * from dbo.sysobjects where id = object_id(N'[dbo].[SolarSystemDistances]') and OBJECTPROPERTY(id, N'IsUserTable') = 1) drop table [dbo].[SolarSystemDistances] CREATE TABLE [dbo].[SolarSystemDistances] ( [FromSolarSystemID] [int] NOT NULL , [ToSolarSystemID] [int] NOT NULL , [Distance] [int] NOT NULL, CONSTRAINT [PK_SolarSystemDistances] PRIMARY KEY CLUSTERED ( [FromSolarSystemID], [ToSolarSystemID] ) ) /* Find accessible jumps so that inaccessible jumps can be ignored in latter calculations Jita (30000142) is used as the root system Records are stored in a new table for faster access */ INSERT INTO SolarSystemJumps SELECT fromSolarSystemID, toSolarSystemID FROM mapSolarSystemJumps WHERE fromSolarSystemID = 30000142 WHILE @@ROWCOUNT > 0 BEGIN INSERT INTO SolarSystemJumps SELECT fromSolarSystemID, toSolarSystemID FROM mapSolarSystemJumps WHERE fromSolarSystemID IN ( SELECT ToSolarSystemID FROM SolarSystemJumps ) AND toSolarSystemID NOT IN ( SELECT ToSolarSystemID FROM SolarSystemJumps WHERE FromSolarSystemID = mapSolarSystemJumps.fromSolarSystemID ) END  Populate distances table with inital values for 1 jump range. INSERT INTO SolarSystemDistances SELECT FromSolarSystemID, ToSolarSystemID, 1 FROM SolarSystemJumps
RETURN
Had to put my code in paste bin since it won't ft into the character limit here. Stored proc 'SolarSystemJumps' is just this: Quote:
SELECT * FROM SolarSystemJumps RETURN
This solution is very fast indeed. I use it to calculate multiwaypoint routes in my EMMA application. (Note that this does not solve the problem of multiwaypoint routes in itself but it is an important component.) It can handle different weights for highsec, lowsec and nosec. It also has a few optimizations compared to a 'clean' Djikstra implementation. I spent a long time working on this and doing LOTS of profiling of various different methods and this solution is as good as I could make it. If you have any questions, just give me a shout. 
