//How would you implement this in PL/SQL ?
Have a look at
http://hansolav.net/blog/ImplementingDijkstrasAlgorithmUsingTSQL.aspx?
PB
mgainty@stripped wrote:
> Good Evening Peter-
>
> //so if I look at this algorithm from wikopedia I see something like
> //Java/C#/C++ no problem
> //How would you implement this in PL/SQL ?
>
> public Dictionary CalculateMinCost(Location _startLocation)
> {
> //Initialise a new empty route list
> Dictionary _shortestPaths = new Dictionary();
> //Initialise a new empty handled locations list
> List _handledLocations = new List();
>
> //Initialise the new routes. the constructor will set the route weight
> to in.max
> foreach (Location location in _locations)
> {
> _shortestPaths.Add(location, new Route(location.Identifier));
> }
>
> //The startPosition has a weight 0.
> _shortestPaths[_startLocation].Cost = 0;
>
> //If all locations are handled, stop the engine and return the result
> while (_handledLocations.Count != _locations.Count)
> {
> //Order the locations
> List _shortestLocations = (List < Location > )(from s in
> _shortestPaths
> orderby s.Value.Cost
> select s.Key).ToList();
>
> Location _locationToProcess = null;
>
> //Search for the nearest location that isn't handled
> foreach (Location _location in _shortestLocations)
> {
> if (!_handledLocations.Contains(_location))
> {
> //If the cost equals int.max, there are no more possible
> connections
> //to the remaining locations
> if (_shortestPaths[_location].Cost == int.MaxValue)
> return _shortestPaths;
> _locationToProcess = _location;
> break;
> }
> }
>
> //Select all connections where the startposition is the location to
> Process
> var _selectedConnections = from c in _connections
> where c.A == _locationToProcess
> select c;
>
> //Iterate through all connections and search for a connection which
> is shorter
> foreach (Connection conn in _selectedConnections)
> {
> if (_shortestPaths[conn.B].Cost > conn.Weight +
> _shortestPaths[conn.A].Cost)
> {
> _shortestPaths[conn.B].Connections =
> _shortestPaths[conn.A].Connections.ToList();
> _shortestPaths[conn.B].Connections.Add(conn);
> _shortestPaths[conn.B].Cost = conn.Weight +
> _shortestPaths[conn.A].Cost;
> }
> }
> //Add the location to the list of processed locations
> _handledLocations.Add(_locationToProcess);
> }
>
> return _shortestPaths;
> }
>
> Thanks
> Martin-
> ----- Original Message -----
> Wrom: PKYLEJGDGVCJVTLBXFGGMEPYOQKEDOTWFAOBUZXUWLSZL
> To: <mysql@stripped>
> Sent: Saturday, March 01, 2008 7:19 PM
> Subject: Re: Efficiently storing a directed graph
>
>
>
>> Kelly,
>>
>>
>>> I'm not married to using SQL: are there other efficient solutions to
>>> store directed graphs? Could I hack something up in Perl or Ruby and
>>> then serialize my in-memory graph to a file (for efficient
>>> saving/reloading)?
>>>
>> Did you look at Dijkstra's algorithm?
>>
>> PB
>>
>> --
>> MySQL General Mailing List
>> For list archives: http://lists.mysql.com/mysql
>> To unsubscribe: http://lists.mysql.com/mysql?unsub=1
>>
>>
>>
>
>
>
>
