Click here to Skip to main content
13,195,379 members (60,098 online)
Click here to Skip to main content
Add your own
alternative version


82 bookmarked
Posted 25 Oct 2011

Dijkstra's Minimum Distance

, 27 May 2012
Rate this:
Please Sign up or sign in to vote.
A .NET implementation of Dijkstra’s for finding the minimum distance path between two nodes in a connected, undirected graph.


The following article exemplifies a .NET implementation of Dijkstra’s for finding the minimum distance path between two nodes in a connected, undirected graph. For the purpose, the technologies that have been used are .NET 4.0, Visual Studio 10, and WPF for the graphical user interface.


The basic elements of every graph are the node and the edge. In general, a graph is an abstraction that could represent anything. The easiest way to think of it (especially for this article) is as a map whereby the nodes are cities and the edges are the connected roads. However, graphs can be used to represent other things as well.

Basic Elements

A single node in this specific example has several important properties – a label that differentiates it from all others, a set of edges that connect it to others, a property that will indicate whether the node has been visited or not, its coordinates that will be used in its graphical representation, and total cost. We will talk more about the notion total cost later. It is the basis of comparison, which will help us determine which node to select next.

An edge is a connection between two nodes in a graph. There are two kinds of edges – directed and undirected. A directed edge can be viewed as a one-way street. It indicates that while there is a path from node A to node B, going in the opposite direction (from B to A) is not possible. In order to do that, we will need another edge that connects A and B and whose direction points to A. An undirected edge, on the other hand, does not impose such limitations and allows us to go in both directions. The properties that are important for an edge are the end nodes that it connects, whether the edge has been visited or not, its weight and direction, if there is such. 

Generally, a graph has only one type of edge. Depending on the kind of edges a graph has, it is qualified as directed or undirected. In this example, we will be looking at undirected graphs. These two elements have their respective implementation in the example: the classes Node and Edge. In addition, there are two other data structures that help us with the execution of the algorithm in terms of clarity and speed at the same time: the classes ReachableNode and ReachableNodeList. These two helper classes will allow us to sort unvisited nodes according to their total cost quickly and select the best one and do it in the most efficient manner.

The Algorithm

Dijkstra’s algorithm for finding the shortest path between two nodes in a graph is generally characterized as a “greedy” algorithm. That is to say that at every step of the way, the algorithm will choose the node that has the lowest total cost and that has not been visited.

Let’s take a simple example like the one below and try to run the algorithm by hand to see what needs to be done each step of the way. Imagine that we want to go from node 1 to node 8. We start by considering all neighbors (or as referred to in the code samples - reachable nodes) to the starting node – nodes 2, 4, and 5. Going from 1 to 2 will generate a cost of 21, from 1 to 5 – 13, and from 1 to 4 – 27. Our best option is to go from 1 to 5. At this point, we note the fact that we have visited nodes 1 and 5 as well as the edge connecting them. What is more, we note that we came to node 5 through the edge that connects nodes 1 and 5.

Now we are at node 5. Since node 5 is not the desired destination, we will run another iteration of the algorithm. We discover all additional reachable nodes from this current position – nodes 3 and 6. We exclude node 1, since it has already been visited (this is where we actually started). The total cost so far is 13.

Nodes 2 and 4 are equally good since in both cases the total cost will be 13 + 18 = 31. For node 6, the total cost would be 35, and for node 3 – 49. Even though these two options are not the best ones for the time being, we will keep them aside since they might become attractive, if we run out of other options. Since going to node 2 is equivalent to going to node 4, let’s consider that scenario. When we get to node 2, our total cost is 31 and we can only go to node 6 since we have visited nodes 1 and 5. This would incur a total cost of 31 + 51 = 82. This is not the best option, since we could go from node 5 to 4 where the total cost would be 31. We mark node 2 and the edge 5 – 2 as visited, and we note that we got to node 2 from node 5. Now we are at node 4 and our total cost is 31. From here, we can go to nodes 3 and 7, which yields a total cost of 40 and 49, respectively. We have a better option – to go from 5 to 6, which gives a total cost of 13 + 22 = 35. As usual, we mark node 6 as visited and we remember that we visited it through the edge coming from node 5.

From the options that we are left with, there are two that are equivalent. We could go from 4 to 3 and from 6 to 8 at a total cost of 40. Let’s assume that we will first consider the first option. We mark node 3 as visited and the fact that we got there from node 4. At this point, the only nodes that have not been visited are 7 and 8. The options that we have are to go from 4 to 7, 3 to 7, 3 to 8, and 6 to 8, resulting in 49, 48, 50, and 40 total cost, respectively. Our best option is to go from 6 to 8 where we reach our final destination. At this point, we have completed the task. What is left to do is to highlight the best path. This is relatively easy to do because each step of the way we noted the edge from which we visited the node. Therefore, what we need to do is simply follow our way backwards. We start at node 8 and we came to it from node 6. We got at node 6 from node 5, and we got at node 5 from node 1. As a result, the minimum distance path from 1 to 8 is 1 – 5 – 6 – 8, with a total cost of 40.

Using the Application

In order to use the application, first the user needs to create the nodes and the edges between them. To create a node, the user needs to click on the canvas. In order to connect two nodes, the user needs to consecutively select two nodes created on the canvas. Similarly, to find the minimum distance between two nodes, the user needs to click on the “Find Min Distance” button and select two nodes on the canvas. The “Clear” button allows the user to clear the canvas and build a new graph. “Restart” allows the user to go back to the initial condition of the graph before finding the minimum distance.


This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)


About the Author

Apostol Bakalov
Software Developer
Bulgaria Bulgaria
No Biography provided

You may also be interested in...

Comments and Discussions

QuestionNot working as described Pin
Member 1327122721-Jun-17 13:49
memberMember 1327122721-Jun-17 13:49 
AnswerRe: Not working as described Pin
Apostol Bakalov4-Jul-17 22:44
memberApostol Bakalov4-Jul-17 22:44 
QuestionDoesn't Work Pin
DMardell6-Jul-13 3:25
memberDMardell6-Jul-13 3:25 
Questionweldone Pin
Williams adesola10-Nov-12 3:43
memberWilliams adesola10-Nov-12 3:43 
GeneralDirected graph algorithm Pin
madhurisamudrala11-Jul-12 19:18
membermadhurisamudrala11-Jul-12 19:18 
QuestionDoesn't Look Right Pin
Ted Goulden28-May-12 18:05
memberTed Goulden28-May-12 18:05 
AnswerRe: Doesn't Look Right Pin
Apostol Bakalov29-May-12 11:21
memberApostol Bakalov29-May-12 11:21 
Question[My vote of 1] Discussion of data structures? Pin
Maniezzo27-May-12 23:36
memberManiezzo27-May-12 23:36 
AnswerRe: [My vote of 1] Discussion of data structures? Pin
Apostol Bakalov28-May-12 0:40
memberApostol Bakalov28-May-12 0:40 
GeneralRe: [My vote of 1] Discussion of data structures? Pin
Maniezzo28-May-12 2:58
memberManiezzo28-May-12 2:58 
GeneralRe: [My vote of 1] Discussion of data structures? Pin
Apostol Bakalov28-May-12 9:52
memberApostol Bakalov28-May-12 9:52 
GeneralRe: [My vote of 1] Discussion of data structures? Pin
Maniezzo28-May-12 10:16
memberManiezzo28-May-12 10:16 
GeneralOk but Not Good Pin
minhtiennguyen20-Mar-12 4:13
memberminhtiennguyen20-Mar-12 4:13 
GeneralRe: Ok but Not Good Pin
Apostol Bakalov20-Mar-12 13:37
memberApostol Bakalov20-Mar-12 13:37 
GeneralRe: Ok but Not Good Pin
minhtiennguyen20-Mar-12 15:01
memberminhtiennguyen20-Mar-12 15:01 
GeneralRe: Ok but Not Good Pin
Apostol Bakalov21-Mar-12 13:52
memberApostol Bakalov21-Mar-12 13:52 
GeneralRe: Ok but Not Good Pin
Apostol Bakalov27-May-12 1:14
memberApostol Bakalov27-May-12 1:14 
QuestionGreat..But... Pin
Omar Gamil17-Dec-11 23:40
memberOmar Gamil17-Dec-11 23:40 
AnswerRe: Great..But... Pin
Apostol Bakalov20-Mar-12 13:38
memberApostol Bakalov20-Mar-12 13:38 
Indeed, you are right that the actual algorithm could be separated from the UI. In fact, as the project is, it is relatively easy to do. I will try to take some time to do that. Thanks for the suggestion.
QuestionGreate..But... Pin
Omar Gamil17-Dec-11 23:40
memberOmar Gamil17-Dec-11 23:40 
QuestionThe graph needn't be undirected Pin
Dennis Dykstra1-Nov-11 6:44
memberDennis Dykstra1-Nov-11 6:44 
AnswerRe: The graph needn't be undirected Pin
Apostol Bakalov2-Nov-11 4:26
memberApostol Bakalov2-Nov-11 4:26 
QuestionQuickgraph Pin
Daniel Brännström26-Oct-11 1:10
memberDaniel Brännström26-Oct-11 1:10 
AnswerRe: Quickgraph Pin
Apostol Bakalov26-Oct-11 2:13
memberApostol Bakalov26-Oct-11 2:13 
QuestionCool, we did A* / Djistras at uni, loved all that stuff. Pin
Sacha Barber25-Oct-11 21:54
mvpSacha Barber25-Oct-11 21:54 

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.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.171019.1 | Last Updated 27 May 2012
Article Copyright 2011 by Apostol Bakalov
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid