Wireless Routing using Dijkstra's Shortest Path Algorithm

Summary

Explains Dijkstra's shortest path algorithm, for wireless network routing. The users can create a random map with dynamic transmission range and choose a source and destination mobile node (by clicking) in the map and see the shortest path visually in the Silverlight output.

Silverlight Screenshot

Source Code

The Node class represents a mobile node. The Map class represents a set of nodes (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; }
}

The following code implements the shortest path algorithm for a wireless network (un-directed and un-connected graph), using the transmission range. The data-structures used in this code are defined above.

public static List<Node> FindShortestPath(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);
}