Wednesday, 20 December 2006

School is out for Christmas (I had my last exam last Friday), so now I have time do fun things, like coding (surprise).

I think algorithmic programming and databases and SQL queries are cool things, so why not combine them? Yesterday I got an idea of implementing some well-known algorithm in SQL, and I figured out that Dijkstra's Shortest Path algorithm should be fun to implement.

Dijkstra's shortest path algorithm finds, well, the shortest path from one vertex to the other vertexes in a weighted graph. The edges have lengths (or costs or whatever), and the shortest path from one vertex to another is the path where the sum of these lengths are as small as possible. Take a look at the illustration below, showing a graph with some Norwegian cities. The shortest path from Trondheim to Fredrikstad has been highlighted (for those of you that know Norway, not very realistic, but let's pretend it is just for the fun of it).
djikstra.gif

The algorithm works like a breadth first search that takes the edge weights into account, starting at one vertex and traversing through the graph.

So, how do we implement this in Transact-SQL (MS SQL Server's SQL dialect)? Well, first we need some way to represent the graph. I've created two tables:

City
city.jpg
Road
road.jpg

The City table is pretty straightforward. The Road table contains one row for every road from one city to another, and the length of that road. Notice that we have two rows for every two cities we have a road between them, one each way. But, now to the real stuff: The implementation of the algorithm:

CREATE PROCEDURE [dbo].[Dijkstra]
    @StartCity Int
AS
BEGIN
    -- Automatically rollback the transaction if something goes wrong.    
    SET XACT_ABORT ON    
    BEGIN TRAN
    
    -- SET NOCOUNT ON added to prevent extra result sets from
    -- interfering with SELECT statements.
    SET NOCOUNT ON;

    -- Create a temporary table for storing the estimates as the algorithm runs
    CREATE TABLE #CityList
    (
        CityId Int NOT NULL,    -- The City Id
        Estimate Int NOT NULL,    -- What is the distance to this city, so far?
        Predecessor Int NULL,    -- The city we came from to get to this city with this distance.
        Done bit NOT NULL        -- Are we done with this city yet (is the estimate the final distance)?
    )

    -- Fill the temporary table with initial data
    INSERT INTO #CityList (CityId, Estimate, Predecessor, Done)
    SELECT CityId, 2147483647, NULL, 0 FROM City
    
    -- Set the estimate for the city we start in to be 0.
    UPDATE #CityList SET Estimate = 0 WHERE CityID = @StartCity
    IF @@rowcount <> 1
    BEGIN
        RAISERROR ('Couldn''t set start city', 11, 1)
        ROLLBACK TRAN        
        RETURN
    END

    DECLARE @FromCity Int, @CurrentEstimate Int

    -- Run the algorithm until we decide that we are finished
    WHILE 1=1
    BEGIN
        -- Reset the variable, so we can detect getting no records in the next step.
        SELECT @FromCity = NULL

        -- Select the CityID and current estimate for a city not done, with the lowest estimate.
        SELECT TOP 1 @FromCity = CityId, @CurrentEstimate = Estimate
        FROM #CityList WHERE Done = 0 AND Estimate < 2147483647
        ORDER BY Estimate
        
        -- Stop if we have no more unvisited, reachable cities.
        IF @FromCity IS NULL BREAK

        -- We are now done with this city.
        UPDATE #CityList SET Done = 1 WHERE CityId = @FromCity

        -- Update the estimates to all neighbour cities of this one (all the cities
        -- there are roads to from this city). Only update the estimate if the new
        -- proposal (to go via the current city) is better (lower).
        UPDATE #CityList SET #CityList.Estimate = @CurrentEstimate + Road.Distance,
            #CityList.Predecessor = @FromCity
        FROM #CityList INNER JOIN Road ON #CityList.CityID = Road.ToCity
        WHERE Road.FromCity = @FromCity AND (@CurrentEstimate + Road.Distance) < #CityList.Estimate
        
    END
    
    -- Select the results.
    SELECT City1.Name AS ToCity, Estimate AS Distance, city2.Name AS Predecessor FROM #CityList
    INNER JOIN City city1 ON #CityList.CityId = City1.CityID
    LEFT OUTER JOIN City city2 ON #CityList.Predecessor = city2.CityID
    
    -- Drop the temp table.
    DROP TABLE #CityList
    
    COMMIT TRAN
END

If we run it with Trondheim as start city (@StartCity = 1), we get this result table:

result.jpg

This says that from Trondheim, we have a distance 0 to Trondheim, 2 to Bergen and so on, and 6 to Fredrikstad. The Predecessor column says what city we came from when we went to each city. We can see that to get to Fredrikstad, we came from Oslo, and to get to Oslo, we came from Bergen. To get to Bergen, we came from Trondheim. Therefore, to get to Fredrikstad, we took the path Trondheim, Bergen, Oslo, Fredrikstad.

I have included the SQL script to create the database:

Dijkstra.txt (8,03 KB)
TestScript.txt (1,26 KB)

Sunday, 03 February 2008 15:38:19 (W. Europe Standard Time, UTC+01:00)
Cool, the post.

Thanks for the information.
Monday, 03 March 2008 18:51:49 (W. Europe Standard Time, UTC+01:00)
Hi Hans,

thanks for this great demonstration. but little question: i want tell a StopCity. actually i´ve testet a lot, but didn´t found a solution yet...
ca you give me a hint?
Monday, 03 March 2008 19:45:17 (W. Europe Standard Time, UTC+01:00)
Hi Thomas,

When you say that you want to specify a stop city, what are you trying to achieve? Stopping the algorithm when reaching it (to prevent doing more work than necessary), or calculate the route to that specific city?

I've written a more complete version which I haven't published yet, but you can take a look at it here: http://hansolav.net/sql/graphs.html#dijkstra.
Hans Olav
Tuesday, 04 March 2008 13:23:54 (W. Europe Standard Time, UTC+01:00)
Hi Hans,

thx for the scripts and the realy fast answer!
i see, you use CTE, so SQL-Server have be at least 2005 (we use 2005).
yes, i want calculate the shortest route from one "city" (start) to another one (destination). in your demo for example
@StartCity=Bergen
@DestinationCity=Fredrikstad



Thursday, 06 March 2008 14:27:55 (W. Europe Standard Time, UTC+01:00)
Hi Hans,
my problems are solved. I expanded this code with the CTE from your new script. Now, my "Database-Internal-Navigation" is finished.

Thanks.
Thomas
Thursday, 06 March 2008 16:57:46 (W. Europe Standard Time, UTC+01:00)
Hi Thomas,

Good to hear that you solved it. The code shouldn't be much different from what I've written. If you know the destination, you could make it stop when it reaches it as an optimization. Other than that, it should be enough to filter the results from the CTE at the end.

Feel free to ask if you have other questions.

Hans Olav.
Hans Olav
Sunday, 09 March 2008 18:20:28 (W. Europe Standard Time, UTC+01:00)
How to calculate the route to the specific city?
Wednesday, 08 October 2008 17:54:35 (W. Europe Standard Time, UTC+01:00)
Thanks. I had to write Dijkstra's in Oracle PL/SQL. I reused the data-structures described here (CityList) and converted T-SQL's UPDATE in to Oracle's MERGE INTO and I was pretty much done.

Thanks for sharing this.
Sunday, 17 May 2009 19:57:37 (W. Europe Standard Time, UTC+01:00)
Hi,

I am a Research scientist working on the same problem. This was a really helpful read. Did you write/optimized this research any further. I would be really obliged if you can share your findings.

Thanks,
Vikas.
Monday, 18 May 2009 00:12:26 (W. Europe Standard Time, UTC+01:00)
Hi Vikas,

I did some more work here:
http://hansolav.net/sql/graphs.html#dijkstra

Apart from that, I haven't done any more work on this. I guess a non-T-SQL implementation would be faster, for instance it could be implemented as SQL CLR (.NET in SQL Server).

Just ask if you have any questions. If I'm slow at replying, send me an email at hansolav @ this domain.

Hans Olav.
Hans Olav
Wednesday, 20 May 2009 16:55:36 (W. Europe Standard Time, UTC+01:00)
Good afternoon. Flattery is like cologne water, to be smelt of, not swallowed. Help me! It has to find sites on the: drug addict treatment center. I found only this - <a href="http://design.ru-deluxe.ru/">adobe fotoshop kisti</a>. Thats a good question, to start with we dont provide drug treatment. For alcohol and drug information ncadi. Thank :mad: Paola from Algeria.
Saturday, 23 May 2009 06:19:24 (W. Europe Standard Time, UTC+01:00)
Good morning. A writer is a person for whom writing is more difficult than it is for other people. Help me! Need information about: Turbo Tax. I found only this - <a href="http://turbo-tax.biz">turbo tax</a>. Long term residential drug and alcohol treatment programs offer around the clock. Participants will be recruited from alcohol treatment centers. Waiting for a reply :cool:, Channing from Austria.
Name
E-mail
Home page

Comment (HTML not allowed)  

Enter the code shown (prevents robots):

Live Comment Preview