Click here to Skip to main content
14,691,039 members
Articles » General Programming » Algorithms & Recipes » Path Finding
Posted 3 Jan 2008


74 bookmarked

Dijkstra:Shortest Route Calculation - Object Oriented

Rate me:
Please Sign up or sign in to vote.
4.32/5 (24 votes)
3 Jan 2008CPOL
Calculation of the shortest path between x points
Image 1
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:

  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).


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


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;


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)
        _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<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;

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

    return _shortestPaths;


  • 24 December, 2007: First release


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

No Biography provided

Comments and Discussions

QuestionGUI Representation Pin
Member 1052059213-Jan-14 0:45
MemberMember 1052059213-Jan-14 0:45 
QuestionHow to calculate only cost to a specific node Pin
Martin Ryan14-Dec-13 4:00
MemberMartin Ryan14-Dec-13 4:00 
QuestionTe links to source and demo zips are broken ? Pin
abel406g5-Aug-13 8:25
Memberabel406g5-Aug-13 8:25 
AnswerRe: Te links to source and demo zips are broken ? Pin
Martin Ryan14-Dec-13 4:00
MemberMartin Ryan14-Dec-13 4:00 
GeneralMy vote of 5 Pin
Jocelyn62France4-Jul-12 0:49
MemberJocelyn62France4-Jul-12 0:49 
BugPersistent GUI Pin
Member 842553613-Feb-12 16:50
MemberMember 842553613-Feb-12 16:50 
QuestionPoint to Point searching Pin
maralita4-Sep-11 1:43
Membermaralita4-Sep-11 1:43 
Generalc projct Pin
deepakptl4341@Gmail.com18-Mar-11 8:33
Memberdeepakptl4341@Gmail.com18-Mar-11 8:33 
Generalc progaming Pin
deepakptl4341@Gmail.com18-Mar-11 8:31
Memberdeepakptl4341@Gmail.com18-Mar-11 8:31 
QuestionC++ conversion Pin
xumepoc10-Nov-10 4:18
Memberxumepoc10-Nov-10 4:18 
GeneralSubject Pin
jcdentondx28-May-10 11:13
Memberjcdentondx28-May-10 11:13 
Questionrun time? Pin
Peter Cacioppi3-Jan-10 10:58
MemberPeter Cacioppi3-Jan-10 10:58 
AnswerRe: run time? Pin
Michael Demeersseman4-Jan-10 0:28
MemberMichael Demeersseman4-Jan-10 0:28 
AnswerRe: run time? Pin
Member 1052059213-Jan-14 2:36
MemberMember 1052059213-Jan-14 2:36 
QuestionInstallation on Windows Vista Pin
ssnc17-Mar-09 9:38
Memberssnc17-Mar-09 9:38 
QuestionFile 'usrLocation.cs' not found. Pin
Member 330569822-Apr-08 20:52
MemberMember 330569822-Apr-08 20:52 
AnswerRe: File 'usrLocation.cs' not found. Pin
Michael Demeersseman23-May-08 21:58
MemberMichael Demeersseman23-May-08 21:58 
GeneralBug! Pin
Manjit Dosanjh10-Jan-08 0:46
MemberManjit Dosanjh10-Jan-08 0:46 
GeneralRe: Bug! Pin
Michael Demeersseman10-Jan-08 10:24
MemberMichael Demeersseman10-Jan-08 10:24 
GeneralRe: Bug! Pin
Manjit Dosanjh11-Jan-08 1:03
MemberManjit Dosanjh11-Jan-08 1:03 
GeneralRe: Bug! Pin
Michael Demeersseman23-May-08 21:58
MemberMichael Demeersseman23-May-08 21:58 
QuestionWhat version? Pin
Manjit Dosanjh9-Jan-08 12:40
MemberManjit Dosanjh9-Jan-08 12:40 
GeneralRe: What version? Pin
Manjit Dosanjh10-Jan-08 0:43
MemberManjit Dosanjh10-Jan-08 0:43 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.