New User?   Join Now     Login            Forgot Password?    
Dijkstra's Path Finding  (53697 hits)
 Share this Article
 
Posted by Prabu Arumugam on Aug-29-2010
Languages: C#, Silverlight

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  (1120 downloads) C#, Silverlight 3 Visual Studio 2008

 Share this Article

 Comments on this Article
Comment by Juan Pedro Fisanotti on Jul-29-2015
Nice article and explanation. It could benefit from some graphical explanation too, maybe this visualizations can help people to better understand how dijkstra's algorithm works by looking it in action :) https://thewalnut.io/visualizer/visualize/1006/6/
Comment by Tamber on Sep-08-2014
Hi, thanks so much for the source code
Comment by Prabu on Mar-12-2012
Chaitanya, this example is created for a graph only; here a mobile network is represented in terms of a graph. This graph can be thought of any set of objects that can be connected and are related to each other by some number (in this example, each object is related by 'distance').
Comment by chaitanya on Mar-12-2012
hi, thanks a lot for sharing your knowledge. i have a similar requirement but not for the mobile networks. i couldn't figure out what to use in the place of transmission range, because i am using it for a graph rather than a network. please help me in achieving it. thanks.
Comment by kirti patel on Feb-08-2012
thanks
Comment by berk on Mar-06-2011
is it possible to send us the source codes? thank you
 Post your comment here
Your Name
Your Email
Comment
Post Comment

About      Terms      Contact