Complex C# Linq Algorithm

Question

I have a C# problem to solve. I am creating an application which can determine the shortest route to take. There is a network of ports and the method needs to work out the quickest route to take.

I have got this far with my method but it seems like I am duplicating code and the possible routes could go on forever. Has anyone on got an idea of a better way to test all possibly journeys so I am able to calculate the shortest one ?

 public int ShortestJourneyTime(string startPort, string endPort)
    {
        int shortJourneyTime = 0;
        var possStartRoutes = RouteData.Where(p => p.Key[0] == startPort);

        if (possStartRoutes.Count() <= 0)
            throw new InvalidOperationException(string.Format("{0} : Start port is invalid", startPort));

        foreach (var p in possStartRoutes)
        {
            int currentJourneyTime = p.Value;

            var possRoutes2 = RouteData.Where(p2 => p2.Key[0] == p.Key[1]);

            foreach (var p2 in possRoutes2)
            {
                if (p2.Key[1] == endPort)
                {
                    currentJourneyTime += p2.Value;
                    if (shortJourneyTime > currentJourneyTime || shortJourneyTime == 0)
                        shortJourneyTime = currentJourneyTime;
                }
                else
                {
                    var possRoutes3 = RouteData.Where(p3 => p3.Key[0] == p2.Key[1]);
                }
            }
        }

        return shortJourneyTime;
    }

The port data is stored like below

  Dictionary<List<string>, int>  testData = new Dictionary<List<string>, int>();

        List<string> routeOne = new List<string>() { "Buenos Aires", "New York" };
        testData.Add(routeOne, 6);

Answer 1

As people suggested Dijkstra algorithm. Here is the algorithm for your needs. I kept your data structure Dictionary<List<string>, int> so you can still work with it. But i changed the data structure inside the algorithm and choosed more suitable data structure to make algorithm easier.

The idea is to get all possible paths from start to the end. Then take the shortest path as result. Note that the passed paths should not be duplicated means if we pass New York we should not pass over it again otherwise we fall into infinite loop.

The return type of this method is Tuple<List<string>, int>. where List<string> is the shortest path holding ports in order and int is the length of this path. You can access them with properties Item1 and Item2.

For instance The shortest path from Buenos Aires to Liverpool is this list of string "Buenos Aires","Casablanca","Liverpool" with length of 8 days.

Note that This method returns null if nothing was found. You can throw exception if you want. Just uncomment where i commented throw expetion

Paths in this method are type of Tuple<string, string, int>. Item1 is the start port. Item2 is end port and Item3 is the length between these two ports.

public Tuple<List<string>, int> TakeShortestJourney(string startPort, string endPort)
{
    if (startPort == endPort) // just for special case when user puts same start and end port.
    {
        return new Tuple<List<string>, int>(new List<string>(){startPort}, 0);
    }

    // convert from Dictionary<List<string>, int> into List<Tuple<string, string, int>>
    var t = RouteData.Select(x => new Tuple<string, string, int>(x.Key[0], x.Key[1], x.Value));
    var allPaths = new List<Tuple<string, string, int>>(t);

    // This will hold all possible short paths.
    var passedPaths = new List<Tuple<List<string>, int>>();

    // create a recursion method to do the search and fill the passedPaths.
    Action<List<string>, string, int> getPath = null;
    getPath = (list, start, length) =>
    {
        list.Add(start);

        foreach (
            var currentRoad in
                allPaths.Where(x => !list.Contains(x.Item2) && x.Item1 == start).OrderBy(x => x.Item3))
        {
            int newLength = length + currentRoad.Item3; // calculate new length.

            if (currentRoad.Item2 == endPort)
            {
                list.Add(currentRoad.Item2);
                passedPaths.Add(new Tuple<List<string>, int>(list, newLength));
                break;
            }

            if (passedPaths.Any(x => x.Item2 < newLength)) break;

            getPath(new List<string>(list), currentRoad.Item2, newLength);
        }
    };

    // start search with initial empty list and 0 length. start from startPort
    getPath(new List<string>(), startPort, 0);

    // Take the shortest path from passed paths.
    var shortestPath = passedPaths.OrderBy(x=> x.Item2).FirstOrDefault();

    if (shortestPath == null) {
    //    throw new ApplicationException("nothing was found");
    }

    return shortestPath;
}

Here is example of how to use this method.

var shortestPath = TakeShortestJourney("Buenos Aires", "Liverpool");

foreach (var p in shortestPath.Item1) // Item1 holds path
{
    Console.WriteLine(p);
}

Console.WriteLine(shortestPath.Item2); // Item2 holds length

About the recursion Action:

list.Add(start);

We do this for each call so we build our path with order.

allPaths.Where(x => !list.Contains(x.Item2) && x.Item1 == start).OrderBy(x => x.Item3)

This Query will get the paths that start with start which is end of previous path (x.Item1 == start) but it will not take the paths that already exist in our list to prevent duplicates (!list.Contains(x.Item2)). Finally it will order them by Item3(length) so we take the shortest first (OrderBy(x => x.Item3)).

if (currentRoad.Item2 == endPort)
{
    list.Add(currentRoad.Item2);
    passedPaths.Add(new Tuple<List<string>, int>(list, newLength));
    break;
}

This will check for end of our path. it happens when Item2(end of the current path) is equal to the end port. Finally we add the last item(Item2) to the list, we save our list and the final length together inside the passedPaths. We break the loop because we know the length after this path would be longer because we already reached the end so its unnecessary to continue for the other paths. (remember that we ordered them by Item3)

if (passedPaths.Any(x => x.Item2 < newLength)) break;

This one is just for further optimization Means if there is any complete path exist and the length of the current path is bigger than that, stop building this path since there is shorter path exist. also because the query was ordered, next items have even longer length so we just return from this path. Based on RouteData this may increase or decrease performance. You can safely remove this part without affecting results.

getPath(new List<string>(list), currentRoad.Item2, newLength);

Here is the heart of this algorithm! a recursion call. First parameter is the list that we are making but we create new reference of it each time so the list remains untouched from recursions and we can continue in our foreach loop. Second parameter currentRoad.Item2 is the end of the current path which will be start of the next path. Last parameter newLength, we need this when we save final path in Tuple<List<string>, int>.