复杂的 C# Linq 算法

Question

我有一个 C# 问题需要解决。我正在创建一个可以确定最短路线的应用程序。有一个港口网络，该方法需要计算出最快的路线。

我的方法已经走到这一步了，但似乎我在复制代码，可能的路线可能会永远持续下去。有没有人知道更好的方法来测试所有可能的旅程，以便我能够计算出最短的旅程？

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

端口数据存储如下

  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

正如人们建议的Dijkstra算法。这是满足您需求的算法。我保留了您的数据结构 Dictionary<List<string>, int>，因此您仍然可以使用它。但是我改变了算法内部的数据结构，选择了更合适的数据结构，使算法更容易。

思路是获取从开始到结束的所有可能路径。然后取最短路径作为结果。请注意，传递的路径不应重复意味着如果我们传递 New York 我们不应该再次传递它，否则我们将陷入无限循环。

该方法的return类型为Tuple<List<string>, int>。其中 List<string> 是按顺序保存端口的最短路径，int 是该路径的长度。您可以使用属性 Item1 和 Item2.

访问它们

例如，从 Buenos Aires 到 Liverpool 的最短路径是此字符串列表 "Buenos Aires","Casablanca","Liverpool"，长度为 8 天。

请注意，如果未找到任何内容，此方法 return 为 null。如果你愿意，你可以抛出异常。只是在我评论的地方取消评论 throw expetion

此方法中的路径类型为 Tuple<string, string, int>。 Item1 是起始端口。 Item2 是结束端口，Item3 是这两个端口之间的长度。

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

下面是如何使用此方法的示例。

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

关于递归操作：

list.Add(start);

我们为每次调用都执行此操作，以便我们按顺序构建路径。

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

此查询将获取以 start 开头的路径，这是先前路径 (x.Item1 == start) 的结尾，但它不会采用列表中已存在的路径以防止重复 (!list.Contains(x.Item2)).最后它会按 Item3(length) 排序，所以我们先取最短的 (OrderBy(x => x.Item3)).

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

这将检查我们路径的末端。它发生在 Item2（当前路径的结尾）等于结束端口时。最后我们将最后一项（Item2）添加到列表中，我们将列表和最终长度一起保存在 passedPaths 中。我们打破循环，因为我们知道这条路径之后的长度会更长，因为我们已经到达终点，所以没有必要继续其他路径。（请记住，我们按 Item3 订购了它们）

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

这个只是为了进一步优化意味着如果存在任何完整路径并且当前路径的长度大于该路径，则停止构建该路径，因为存在更短的路径。也因为查询是有序的，下一个项目的长度甚至更长，所以我们只是 return 从这个路径。基于 RouteData 这可能会提高或降低性能。您可以安全地删除此部分而不影响结果。

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

这是该算法的核心！递归调用。第一个参数是我们正在制作的 list 但我们每次都创建它的新引用，因此列表不会受到递归的影响，我们可以继续我们的 foreach 循环。第二个参数 currentRoad.Item2 是当前路径的终点，它将是下一条路径的起点。最后一个参数 newLength，我们在 Tuple<List<string>, int>.

中保存最终路径时需要这个

复杂的 C# Linq 算法

Complex C# Linq Algorithm

c#

linq

algorithm

shortest-path