This article explains Dijkstra's shortest path algorithm and applies the concepts to wireless-network routing along with an implementation in C# and Silverlight. The users can create a random map and choose a source and destination node (by clicking) in the map and see the routing visually in the Silverlight output. The full source code in C# and Silverlight is available for download below.
Path-Finding / Wireless-Routing Demo in Silverlight
The following demo illustrates the routing in a wireless-network. You can create a random map and choose a source and destination node (by clicking) and see the resultant path. The number of nodes (mobile phones) and transmission range can be adjusted dynamically. The source code of this demo is available for download below.
What is a Graph?
A Graph data-structure consists of a set of edges (or arcs) that connect a set of nodes (or vertices). Each edge connects two nodes, and contains some value that quantifies the weight (or cost) of connection between those nodes. Edges in a graph can be directed or un-directed. The following image shows a graph with six vertices (nodes) and seven edges.
Graph is an important data-structure in computer science with significant field of interest. It is used in many real-world problems like path finding, network topology, mobile ad-hoc networks (MANETs), sensor networks, remote sensing, etc. The shortest path finding between two nodes in a graph is useful in traveling salesman problem (finding shortest path between two cities), robotics (guiding a robot along a path), routing in wireless-networks (establishing a voice call between two mobile phones), sensor networks (transferring collected data to base-station with minimal battery energy), etc.
For more information on graph data-structure, see http://en.wikipedia.org/wiki/Graph_(data_structure).
Data Structures for this Article
The path-finding algorithm is illustrated using a set of 2-dimensional (2D) points. Each point corresponds to a node, represented by Node class. A node can be thought of as a city (in traveling salesman problem) or a mobile phone (in wireless-network routing problem). The Map class represents a set of nodes (region/country or a wireless-network).
public class Node
{
public int Id { get; set; }
public double X { get; set; }
public double Y { get; set; }
}
public class Map
{
public List<Node> Nodes { get; set; }
}
Finding the Route from Source to Destination
Edsger Dijkstra's algorithm solves the single-source shortest-path problem. It works for a directed weighted graph, which is a graph that contains a non-negative weight attached to each edge of the graph. For more information on Dijkstra's algorithm, see http://en.wikipedia.org/wiki/Dijkstra's_algorithm.
The algorithm works by repeatedly selecting a neighbor of current node, that is closest to the destination node. That is, in each iteration/hop, the neighbor closest to destination is added to path. For example, if node N5 has four neighbors N3, N4, N6, N7 with distance to destination as 5, 3, 6, 4, then N4 is chosen as the next-node in path. Neighbors already visited (added to path) are ignored. The algorithm starts from source-node and repeats itself until the destination-node is reached or no neighbors are found.
Neighbors of a node are those that are directly connected to that node. If the graph is un-directed or if there are no edges between nodes (un-connected), then the neighbors are chosen based on a domain-specific criteria. In wireless-network routing problem, the neighbor nodes are those that are within the transmission range of current node (mobile phone). This is illustrated in the live demo below.
The following code implements the algorithm for a wireless-network, using the transmission range. The data-structures used in this code are defined above.
public static List<Node> FindRoute(Map map, Node sourceNode, Node destinationNode, double transmissionRange)
{
List<Node> path = new List<Node>();
path.Add(sourceNode);
Node currentNode = sourceNode;
while (true)
{
//get all neighbors of current-node (nodes within transmission range)
List<Node> allNeighbors = map.GetNeighbors(currentNode, transmissionRange);
//remove neighbors that are already added to path
IEnumerable<Node> neighbors = from neighbor in allNeighbors
where !path.Contains(neighbor)
select neighbor;
//stop if no neighbors or destination reached
if (neighbors.Count() == 0) break;
if (neighbors.Contains(destinationNode))
{
path.Add(destinationNode);
break;
}
//choose next-node (the neighbor with shortest distance to destination)
Node nearestNode = FindNearestNode(neighbors, destinationNode);
path.Add(nearestNode);
currentNode = nearestNode;
}
return (path);
}
The function FindNearestNode() finds the node with shortest distance to the destination-node. The distance between two nodes is computed using euclidean distance.
The following function FindNeighbors() defined in Map class is used to find all the neighbors of a given node, within the current transmission range.
public List<Node> GetNeighbors(Node currentNode, double transmissionRange)
{
List<Node> neighbors = new List<Node>();
foreach (Node node in this.Nodes)
{
if (!node.Equals(currentNode)) //ensure current-node itself is not taken as neighbor
{
if (PathFinding.FindDistance(currentNode, node) <= transmissionRange)
{
neighbors.Add(node);
}
}
}
return (neighbors);
}
Downloads for this article
File |
Language |
Tools |
ShortestPath-Demo-Source 53.2 kb (900 downloads) |
C#, Silverlight 3 |
Visual Studio 2008 |