c# - 如何制作伦敦地铁的加权图

Question

我想知道是否有人对如何制作伦敦地铁的加权图有任何建议。它适用于一个项目，因此可以在 Dijkstra 的最短路径算法中使用。

Dijkstra 算法部分很好，我可以做简单的图表。但是地下空间很大，有我需要的所有 250 个节点。

所以想知道是否有任何简单的方法可以解决这个问题？

下图是这种情况下地下车站之间的时间(边权重)的图片。

如有任何建议或帮助，我们将不胜感激。

Answer 1

一个相当简单的表示是使用 MultiValueDictionary，即将单个值映射到值集合的字典。您可以围绕 Dictionary<TKey, List<T>> 制作自己的包装器，或使用 Microsoft.Experimental.Collections 中的一个.例如:

MultiValueDictionary<Station, (Station station, double time)) edges;

void AddConnection(Station from, Station to, double time){
   edges.Add(from, (to, time));
   edges.Add(to, (from, time));
}

其他可能的表示包括

• 表格，只是一个大型二维矩阵，其中每个单元格定义行站和列站之间的遍历时间，或者如果连接不存在则为无效值。缺点是这将是不必要的大，因为大多数站点只连接到另外两个站点。
• 对象，创建一个站对象，其中包含与其他站的连接列表。

您可能应该获取一个定义您的站点的文件，并定义一个函数来解析该文件并构建您的图形。希望您已经有了这样的文件，这样您就不必手动输入每条边

一旦你有了一个基本的实现，我建议你尝试让你的算法使用某种图形表示。您还可以尝试使您的实现通用化，以使用任何类型的节点。我使用的签名看起来像这样:

    public class Djikstra<T>  where T : IEquatable<T>
    {
        public (T FoundNode, double TotalCost) Search(
            IEnumerable<T> from,
            IEnumerable<T> to,
            Func<T, IReadOnlyCollection<(T Node, double Cost)>> graphIterator)
}

当与 multivalueDictionary 一起使用时，这将被称为这样的东西

djikstra.Search(new []{fromStation}, new []{toStation}, n => edges[n]);