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.
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.
Information about Dijkstra can be found here.
Using the Code
The code contains two Project classes:
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.
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.
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.
Location: Just a location (for example 1).
RouteEngine: This class will calculate all routes from one given
Route: This class holds the information about a route between two points (generated with the
The most simple class. It only holds a name to display.
This class contains two
Locationobjects and a
public Connection(Location a, Location b, int weight)
this._a = a;
this._b = b;
this._weight = weight;
This class contains a route. It has only a list of connections and the total weight. This class is generated by the route engine.
This is the class that drives the component. The algorithm is as follows:
- Set the
- Set the total weight to all routes to infinite
- Iterate through all connections of the active position and store their weight if their weight is smaller than their current weight
- Set the active position as used
- Set the nearest point (on whatever location) that isn't used as active
- Repeat 3, 4, 5 until all positions are used
The following method will perform all these steps (and some extra checking and thinking). The
Dictionaryreturned is a list of destination locations and the corresponding route to each destination location.
public Dictionary<location, /> CalculateMinCost(Location _startLocation)
Dictionary<location, /> _shortestPaths = new Dictionary<location, />();
List<location /> _handledLocations = new List<location />();
foreach (Location location in _locations)
_shortestPaths.Add(location, new Route(location.Identifier));
_shortestPaths[_startLocation].Cost = 0;
while (_handledLocations.Count != _locations.Count)
List<location /> _shortestLocations = (List < Location > )(from s in _shortestPaths
Location _locationToProcess = null;
foreach (Location _location in _shortestLocations)
if (_shortestPaths[_location].Cost == int.MaxValue)
_locationToProcess = _location;
var _selectedConnections = from c in _connections
where c.A == _locationToProcess
foreach (Connection conn in _selectedConnections)
if (_shortestPaths[conn.B].Cost > conn.Weight + _shortestPaths[conn.A].Cost)
_shortestPaths[conn.B].Cost = conn.Weight + _shortestPaths[conn.A].Cost;
- 24 December, 2007: First release