12,508,185 members (55,449 online)
alternative version

40.7K views
80 bookmarked
Posted

# Dijkstra's Minimum Distance

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

## Share

 Software Developer Bulgaria
No Biography provided

## You may also be interested in...

 Pro Pro

 First Prev Next
 Doesn't Work DMardell6-Jul-13 3:25 DMardell 6-Jul-13 3:25
 Doesn't Look Right Ted Goulden28-May-12 18:05 Ted Goulden 28-May-12 18:05
 Re: Doesn't Look Right Apostol Bakalov29-May-12 11:21 Apostol Bakalov 29-May-12 11:21
 [My vote of 1] Discussion of data structures? Maniezzo27-May-12 23:36 Maniezzo 27-May-12 23:36
 Re: [My vote of 1] Discussion of data structures? Apostol Bakalov28-May-12 0:40 Apostol Bakalov 28-May-12 0:40
 Re: [My vote of 1] Discussion of data structures? Maniezzo28-May-12 2:58 Maniezzo 28-May-12 2:58
 Re: [My vote of 1] Discussion of data structures? Apostol Bakalov28-May-12 9:52 Apostol Bakalov 28-May-12 9:52
 Re: [My vote of 1] Discussion of data structures? Maniezzo28-May-12 10:16 Maniezzo 28-May-12 10:16
 Ok but Not Good minhtiennguyen20-Mar-12 4:13 minhtiennguyen 20-Mar-12 4:13
 It runs wrong sometimes
 Re: Ok but Not Good Apostol Bakalov20-Mar-12 13:37 Apostol Bakalov 20-Mar-12 13:37
 Re: Ok but Not Good minhtiennguyen20-Mar-12 15:01 minhtiennguyen 20-Mar-12 15:01
 Re: Ok but Not Good Apostol Bakalov21-Mar-12 13:52 Apostol Bakalov 21-Mar-12 13:52
 Re: Ok but Not Good Apostol Bakalov27-May-12 1:14 Apostol Bakalov 27-May-12 1:14
 Great..But... Omar Gamil17-Dec-11 23:40 Omar Gamil 17-Dec-11 23:40
 Re: Great..But... Apostol Bakalov20-Mar-12 13:38 Apostol Bakalov 20-Mar-12 13:38
 Greate..But... Omar Gamil17-Dec-11 23:40 Omar Gamil 17-Dec-11 23:40
 The graph needn't be undirected Dennis Dykstra1-Nov-11 6:44 Dennis Dykstra 1-Nov-11 6:44
 Re: The graph needn't be undirected Apostol Bakalov2-Nov-11 4:26 Apostol Bakalov 2-Nov-11 4:26
 Quickgraph Daniel Brännström26-Oct-11 1:10 Daniel Brännström 26-Oct-11 1:10
 Re: Quickgraph Apostol Bakalov26-Oct-11 2:13 Apostol Bakalov 26-Oct-11 2:13
 Cool, we did A* / Djistras at uni, loved all that stuff. Sacha Barber25-Oct-11 21:54 Sacha Barber 25-Oct-11 21:54
 Re: Cool, we did A* / Djistras at uni, loved all that stuff. Apostol Bakalov25-Oct-11 22:21 Apostol Bakalov 25-Oct-11 22:21
 Re: Cool, we did A* / Djistras at uni, loved all that stuff. rtybase20-Nov-11 8:41 rtybase 20-Nov-11 8:41
 Last Visit: 31-Dec-99 18:00     Last Update: 28-Sep-16 18:05 Refresh 1