CodePlexProject Hosting for Open Source Software

Dijkstra's Solver is a teaching and learning tool designed to allow users to plot out graphs, generate the list of steps required to find the shortest path via Dijkstra's Algorithm, and to illustrate those steps. It is developed using the .NET framework, mainly written in C#.

Path finding algorithms are often employed by video games in order for characters to navigate around obstacles in order to reach a target location. They are also employed in a great deal other situations, GPS navigation systems use forms of path finding in order to direct people to their desired locations, and network routing protocols also often find it useful or necessary to know the shortest possible path.

A commonly known path finding algorithm is “Dijkstra's Algorithm”, discovered and published in 1959 by Dutch computer scientist “Edsger Dijkstra”. (2) This algorithm is known as a 'graph search algorithm', and is very commonly used and taught in tree and graph theory.

AS Decision 1 mathematics, which is taught in colleges to 16-17 year old students, presently contains this algorithm and how to solve it in written form as part of the curriculum. This is often done by a teacher drawing a graph of joined nodes and then manually solving it, and also by the teacher showing pre-rendered animations of pre-drawn graphs being solved.

The former option gives the teacher the advantage of control over the complexity or simplicity of the graph presented, but can become tedious if multiple examples are required. The latter option, however, takes away the teacher's control over the graph and therefore the examples can often be overly complicated for the skill level of the students, as well as being too simple.

There does exist numerous programs which can create and find the shortest route between two points in a graph e.g. (3), however very few if any of them demonstrate step-by-step how the problem is being solved, making them useful only for checking answers are correct, not easily illustrating why they are correct.

So far, very few, if any, efficient and effective compromises exist between the control of the 'manual' option and the ease with which solutions can be presented using the automated option.

1 - http://en.wikipedia.org/wiki/Pathfinding

2 - http://en.wikipedia.org/wiki/Dijkstra's_Algorithm

3 - http://www.codeproject.com/KB/recipes/ShortestPathCalculation.aspx

Last edited Dec 3, 2010 at 5:52 PM by MrMorley, version 5