12,816,775 members (32,179 online)
alternative version

#### Stats

147.9K views
74 bookmarked
Posted 3 Jan 2008

# Dijkstra:Shortest Route Calculation - Object Oriented

, 3 Jan 2008 CPOL
 Rate this:
Calculation of the shortest path between x points
All points are locations. The connections between the points have a specific weight. Not all connections are bidirectional (a dot marks a start travel point). When Calculate is pressed, all routes from the selected location are calculated. When a route is selected in the listbox, the shortest route is visually shown by coloring the start dots red.
In this example, the shortest route from 0 to 4 is going through location 2, 1 and then 4.

## Introduction

Dijkstra was a Dutch computer scientist who invented a fast and simple way to calculate the shortest path between two points. Many examples I have found on the Internet implement that algorithm but none of them have done it in an Object Oriented way. So I thought of making my own.

## Background

Information about Dijkstra can be found here.

## Using the Code

The code contains two Project classes:

1. `GUI`: Shows the information visually
• To add locations, click on the 'Add Location' button and then click on the map where you want to add locations.
• To add routes, click on the 'Add Location' button to deactivate the add location, then click on a start location, then click on a end location. The weight of the route can be configured on top.
2. `RouteEngine`: Calculates the route

I will only go into details about the `RouteEngine`. How the UI is handled is not so important for this article but if you need information about it, you can always ask.

### Project RouteEngine

1. `Connection`: This class holds the information about the connection between two dots. This is a one directional connection from A (the startpoint is visually shown with a dot) to B with a specific weight attached.
2. `Location`: Just a location (for example 1).
3. `RouteEngine`: This class will calculate all routes from one given `startPoint`.
4. `Route`: This class holds the information about a route between two points (generated with the `RouteEngine `class).

#### Location

The most simple class. It only holds a name to display.

#### Connection

This class contains two `Location `objects and a `weight`.

```public Connection(Location a, Location b, int weight)
{
this._a = a;
this._b = b;
this._weight = weight;
}```

#### Route

This class contains a route. It has only a list of connections and the total weight. This class is generated by the route engine.

#### Route Engine

This is the class that drives the component. The algorithm is as follows:

1. Set the `startPosition `as active
2. Set the total weight to all routes to infinite
3. Iterate through all connections of the active position and store their weight if their weight is smaller than their current weight
4. Set the active position as used
5. Set the nearest point (on whatever location) that isn't used as active
6. Repeat 3, 4, 5 until all positions are used

The following method will perform all these steps (and some extra checking and thinking). The `Dictionary `returned is a list of destination locations and the corresponding route to each destination location.

```/// <summary />
/// Calculates the shortest route to all the other locations
/// </summary />
/// <returns />List of all locations and their shortest route</returns />
public Dictionary<location, /> CalculateMinCost(Location _startLocation)
{
//Initialise a new empty route list
Dictionary<location, /> _shortestPaths = new Dictionary<location, />();
//Initialise a new empty handled locations list
List<location /> _handledLocations = new List<location />();

//Initialise the new routes. the constructor will set the route weight to in.max
foreach (Location location in _locations)
{
}

//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<location /> _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].Cost = conn.Weight + _shortestPaths[conn.A].Cost;
}
}
//Add the location to the list of processed locations
}

return _shortestPaths;
}```

## History

• 24 December, 2007: First release

## Share

 Belgium
No Biography provided

## You may also be interested in...

 First Prev Next
 GUI Representation Member 1052059213-Jan-14 0:45 Member 10520592 13-Jan-14 0:45
 How to calculate only cost to a specific node Martin Ryan14-Dec-13 4:00 Martin Ryan 14-Dec-13 4:00
 Te links to source and demo zips are broken ? abel406g5-Aug-13 8:25 abel406g 5-Aug-13 8:25
 Re: Te links to source and demo zips are broken ? Martin Ryan14-Dec-13 4:00 Martin Ryan 14-Dec-13 4:00
 My vote of 5 Jocelyn62France4-Jul-12 0:49 Jocelyn62France 4-Jul-12 0:49
 Persistent GUI Member 842553613-Feb-12 16:50 Member 8425536 13-Feb-12 16:50
 Point to Point searching maralita4-Sep-11 1:43 maralita 4-Sep-11 1:43
 c projct deepakptl4341@Gmail.com18-Mar-11 8:33 deepakptl4341@Gmail.com 18-Mar-11 8:33
 c progaming deepakptl4341@Gmail.com18-Mar-11 8:31 deepakptl4341@Gmail.com 18-Mar-11 8:31
 C++ conversion xumepoc10-Nov-10 4:18 xumepoc 10-Nov-10 4:18
 Subject jcdentondx28-May-10 11:13 jcdentondx 28-May-10 11:13
 run time? Peter Cacioppi3-Jan-10 10:58 Peter Cacioppi 3-Jan-10 10:58
 Thanks for putting together this coding project.I was wondering if you are interested in upgrading the code slightly to implement a more expected big-O run time? Your version appears to take O(v log(v)) time to find the unexplored node with the minimum working distance. This will lead to an overall run time of O(e + v^2log(v)). Implementing a priority queue to maintain the working distances would result in the "update working distance" step and the "find minimum working distance" step both taking O(log (v)) and thus the full execution taking O(e log(v) + v log (v) ). For cases where e is much smaller than v^2, this implementation will be much faster. In the worst case, where e = v^2, the two run times should be roughly similar. However, the e << v^2 case should be more reflective of a real world distance matrix where each edge represents a relatively short, straight path of direct roadway. I could put together a priority queue C# implementation if you are interested in seeing one. The easiest implementation would involve maintaining a List whereby each node could find it's parents and children based on simple modulo/rounding arithmetic of it's index. You would then simply maintain the invariant that a parent node always has a key value less than or equal to that of it's children. CheersPete
 Re: run time? Member 1052059213-Jan-14 2:36 Member 10520592 13-Jan-14 2:36
 Installation on Windows Vista ssnc17-Mar-09 9:38 ssnc 17-Mar-09 9:38
 Bug! Manjit Dosanjh10-Jan-08 0:46 Manjit Dosanjh 10-Jan-08 0:46
 Re: Bug! Manjit Dosanjh11-Jan-08 1:03 Manjit Dosanjh 11-Jan-08 1:03