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

For more explanation of how this algorithm is implemented in C# and Silverlight, and to see the live usable demo, visit: http://www.codeding.com/articles/dijkstras-path-finding

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);
}