Click here to Skip to main content
15,867,453 members
Articles / Desktop Programming / WPF

Dijkstra's Minimum Distance

Rate me:
Please Sign up or sign in to vote.
4.80/5 (34 votes)
27 May 2012GPL36 min read 68.6K   5.7K   82   27
A .NET implementation of Dijkstra’s for finding the minimum distance path between two nodes in a connected, undirected graph.

Introduction 

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.

Background

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.

Image 1

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.

Image 2

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.

Image 3

License

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


Written By
Software Developer
Bulgaria Bulgaria
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionNot working as described Pin
Member 1327122721-Jun-17 13:49
Member 1327122721-Jun-17 13:49 
AnswerRe: Not working as described Pin
Apostol Bakalov4-Jul-17 22:44
Apostol Bakalov4-Jul-17 22:44 
QuestionDoesn't Work Pin
DMardell6-Jul-13 3:25
DMardell6-Jul-13 3:25 
Questionweldone Pin
Williams adesola10-Nov-12 3:43
Williams adesola10-Nov-12 3:43 
GeneralDirected graph algorithm Pin
madhurisamudrala11-Jul-12 19:18
madhurisamudrala11-Jul-12 19:18 
QuestionDoesn't Look Right Pin
Ted Goulden28-May-12 18:05
Ted Goulden28-May-12 18:05 
AnswerRe: Doesn't Look Right Pin
Apostol Bakalov29-May-12 11:21
Apostol Bakalov29-May-12 11:21 
Question[My vote of 1] Discussion of data structures? Pin
Maniezzo27-May-12 23:36
professionalManiezzo27-May-12 23:36 
AnswerRe: [My vote of 1] Discussion of data structures? Pin
Apostol Bakalov28-May-12 0:40
Apostol Bakalov28-May-12 0:40 
GeneralRe: [My vote of 1] Discussion of data structures? Pin
Maniezzo28-May-12 2:58
professionalManiezzo28-May-12 2:58 
GeneralRe: [My vote of 1] Discussion of data structures? Pin
Apostol Bakalov28-May-12 9:52
Apostol Bakalov28-May-12 9:52 
GeneralRe: [My vote of 1] Discussion of data structures? Pin
Maniezzo28-May-12 10:16
professionalManiezzo28-May-12 10:16 
GeneralOk but Not Good Pin
tienbka8820-Mar-12 4:13
tienbka8820-Mar-12 4:13 
GeneralRe: Ok but Not Good Pin
Apostol Bakalov20-Mar-12 13:37
Apostol Bakalov20-Mar-12 13:37 
GeneralRe: Ok but Not Good Pin
tienbka8820-Mar-12 15:01
tienbka8820-Mar-12 15:01 
GeneralRe: Ok but Not Good Pin
Apostol Bakalov21-Mar-12 13:52
Apostol Bakalov21-Mar-12 13:52 
GeneralRe: Ok but Not Good Pin
Apostol Bakalov27-May-12 1:14
Apostol Bakalov27-May-12 1:14 
QuestionGreat..But... Pin
Omar Gameel Salem17-Dec-11 23:40
professionalOmar Gameel Salem17-Dec-11 23:40 
AnswerRe: Great..But... Pin
Apostol Bakalov20-Mar-12 13:38
Apostol Bakalov20-Mar-12 13:38 
QuestionGreate..But... Pin
Omar Gameel Salem17-Dec-11 23:40
professionalOmar Gameel Salem17-Dec-11 23:40 
QuestionThe graph needn't be undirected Pin
Dennis Dykstra1-Nov-11 6:44
Dennis Dykstra1-Nov-11 6:44 
I like this article and your implementation of Dijkstra's algorithm. My only comment is that the graph needn't be undirected. You can have two-way edges with a different cost in each direction along any particular edge. Dijkstra's original article, in fact, points this out; see his "Remark 1" in the original article.

Reference: Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik 1: 269–271.[^].
AnswerRe: The graph needn't be undirected Pin
Apostol Bakalov2-Nov-11 4:26
Apostol Bakalov2-Nov-11 4:26 
QuestionQuickgraph Pin
Daniel Brännström26-Oct-11 1:10
Daniel Brännström26-Oct-11 1:10 
AnswerRe: Quickgraph Pin
Apostol Bakalov26-Oct-11 2:13
Apostol Bakalov26-Oct-11 2:13 
QuestionCool, we did A* / Djistras at uni, loved all that stuff. Pin
Sacha Barber25-Oct-11 21:54
Sacha 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.