Finding Shortest Path Recursively

• Download demo project - 3.8 KB
• Download source - 36.8 KB

Introduction

There are several ways to find the shortest path in a given path collection from a starting point to target point. In this tip, I will try to show how to find the shortest path recursively. The main idea is, a walker walks through all possible paths to reach the target point and decides the shortest path. This manner is the most cost-efficient way, but this is just another solution to find the shortest path.

Using the Code

There are 2 classes. One of them is the Path class that simulates a path, having two points and a distance value. Path is considered as one directional.

/// <summary>
/// Definition of a path
/// </summary>
public class Path
{
    //beginning and ending points
    string startingPoint, endingPoint;

    //distance of path
    double distance;
    ...

The other class is the Walker class. This class is the main actor of the program. Holds all paths, walks from a starting point to target point to find all possibilities and decides the shortest path.

// <summary>
/// Main actor of application.
/// Holds full paths
/// Walks through all combination of path to reach target point.
/// starts walking from a starting point
/// </summary>
public class Walker
{
    string startingPoint = string.Empty, targetPoint = string.Empty;

    //Holds all paths in memory
    List<Path> allPaths;

    //contains the shortest path
    List<Path> shortestPath;

    //contains currently experiencing path
    List<Path> currentPath;
    ...

The most important method of walker class is Experience(string point). Walker walks through all possible paths and decides the shortest path.

/// <summary>
/// Experience all combination of paths from a given point
/// </summary>
/// <param name="point"></param>
public void Experience(string point)
{
    Console.WriteLine("Experiencing all paths from point {0}", point);
    List<Path> availablePaths = GetAvailablePaths(point);
    foreach (Path path in availablePaths)
    {
        if (Move(path))
        {
            //if target point is reached then check whether current path is shorter than shortestPath
            if (path.EndingPoint == this.targetPoint)
            {
                //Decide if current path is shorter than shortest path
                if(TotalDistance(this.shortestPath) == 0 || 
                TotalDistance(this.shortestPath) > TotalDistance(this.currentPath))
                    SetShortestPath(this.currentPath);
            }
            else
                //try to reach targetpoint by walking recursively available paths
                Experience(path.EndingPoint);
        }
        //After experiencing all paths from point go back to get the original state of current path
        this.currentPath.Remove(path);
    }
    Console.WriteLine("Experienced all paths from point {0}", point);
}

Points of Interest

Although the title is written as 'Finding shortest path', it is possible to find other paths, such as longest path, path that has minimum or maximum steps, etc. Just change decision making in Experience(string point) method. Path is considered as one directional. If a point A to B is defined, then defining a path that is B to C can simulate two directional.

History

• September 11, 2014: Added ShortestPathRecursively