Click here to Skip to main content
Click here to Skip to main content

Dijkstra's Minimum Distance

, 27 May 2012 GPL3
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.

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.

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.

License

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

Share

About the Author

Apostol Bakalov
Software Developer
Bulgaria Bulgaria
No Biography provided

Comments and Discussions

 
QuestionDoesn't Work PinmemberDMardell6-Jul-13 3:25 
Questionweldone PinmemberWilliams adesola10-Nov-12 3:43 
GeneralDirected graph algorithm Pinmembermadhurisamudrala11-Jul-12 19:18 
QuestionDoesn't Look Right PinmemberTed Goulden28-May-12 18:05 
AnswerRe: Doesn't Look Right PinmemberApostol Bakalov29-May-12 11:21 
Question[My vote of 1] Discussion of data structures? PinmemberManiezzo27-May-12 23:36 
AnswerRe: [My vote of 1] Discussion of data structures? PinmemberApostol Bakalov28-May-12 0:40 
GeneralRe: [My vote of 1] Discussion of data structures? PinmemberManiezzo28-May-12 2:58 
GeneralRe: [My vote of 1] Discussion of data structures? PinmemberApostol Bakalov28-May-12 9:52 
GeneralRe: [My vote of 1] Discussion of data structures? PinmemberManiezzo28-May-12 10:16 
GeneralOk but Not Good Pinmemberminhtiennguyen20-Mar-12 4:13 
GeneralRe: Ok but Not Good PinmemberApostol Bakalov20-Mar-12 13:37 
GeneralRe: Ok but Not Good Pinmemberminhtiennguyen20-Mar-12 15:01 
GeneralRe: Ok but Not Good PinmemberApostol Bakalov21-Mar-12 13:52 
GeneralRe: Ok but Not Good PinmemberApostol Bakalov27-May-12 1:14 
QuestionGreat..But... PinmemberOmar Gamil17-Dec-11 23:40 
AnswerRe: Great..But... PinmemberApostol Bakalov20-Mar-12 13:38 
QuestionGreate..But... PinmemberOmar Gamil17-Dec-11 23:40 
QuestionThe graph needn't be undirected PinmemberDennis Dykstra1-Nov-11 6:44 
AnswerRe: The graph needn't be undirected PinmemberApostol Bakalov2-Nov-11 4:26 
QuestionQuickgraph PinmemberDaniel Brännström26-Oct-11 1:10 
AnswerRe: Quickgraph PinmemberApostol Bakalov26-Oct-11 2:13 
QuestionCool, we did A* / Djistras at uni, loved all that stuff. PinmvpSacha Barber25-Oct-11 21:54 
AnswerRe: Cool, we did A* / Djistras at uni, loved all that stuff. PinmemberApostol Bakalov25-Oct-11 22:21 
GeneralRe: Cool, we did A* / Djistras at uni, loved all that stuff. Pinmemberrtybase20-Nov-11 8:41 

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

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

| Advertise | Privacy | Mobile
Web02 | 2.8.141015.1 | Last Updated 27 May 2012
Article Copyright 2011 by Apostol Bakalov
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid