快速图库中的加权有向图

Question

以下是我的问题示例。

我想用C#编写代码，以便我可以查询结构并查找信息，例如：

• A到B的总距离。
• A到E的最短距离（请记住，您不能违反箭头的方向）。

因此，我想使用邻接表来模拟我的图形，但后来我想这是一种常见的事情，并开始寻找帮助加快过程的库（不需要重新发明轮子等等）。

我发现这个库在各种主题上被推荐了几次，但我发现很难对上面画出的图进行建模。

- J86

Answer 1

一种可能的解决方案是将你的图建模为一个 AdjacencyGraph<string, Edge<string>>，并构建一个Dictionary<Edge<string>, double>代表成本字典，其中成本就是你的距离。

// ...
private AdjacencyGraph<string, Edge<string>> _graph;
private Dictionary<Edge<string>, double> _costs;

public void SetUpEdgesAndCosts()
{
    _graph = new AdjacencyGraph<string, Edge<string>>();
    _costs = new Dictionary<Edge<string>, double>();

    AddEdgeWithCosts("A", "D", 4.0);
    // snip
    AddEdgeWithCosts("C", "B", 1.0);
}

private void AddEdgeWithCosts(string source, string target, double cost)
{
    var edge = new Edge<string>(source, target);
    _graph.AddVerticesAndEdge(edge);
    _costs.Add(edge, cost);
}

你的_graph现在是：

接着，你可以使用以下方法找到从A到E的最短路径：

private void PrintShortestPath(string @from, string to)
{
    var edgeCost = AlgorithmExtensions.GetIndexer(_costs);
    var tryGetPath = _graph.ShortestPathsDijkstra(edgeCost, @from);

    IEnumerable<Edge<string>> path;
    if (tryGetPath(to, out path))
    {
        PrintPath(@from, to, path);
    }
    else
    {
        Console.WriteLine("No path found from {0} to {1}.");
    }
}

这是根据QuickGraph Wiki改编的内容。它会输出：

Path found from A to E: A > D > B > E

- Marijn

---

在Github上的工作示例链接。 - Marijn