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.
