QuickGraph库中的加权有向图

Question

这是我的问题的一个例子.

我想以这种方式在C#中对此进行编码,以便我可以查询结构并查找如下信息:

• 从A到B的总距离.
• 从A到E的最短距离(请记住,你不能逆着箭头的方向).

所以我认为我会使用邻接列表来模拟我的图形,但后来我认为这是常见的事情,并开始寻找库以帮助加快过程(无需重新发明轮子等等)

我偶然发现了这个图书馆,在各种主题上推荐了几次,但我发现上面绘制的图形真的很难建模.

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维基改编的.它打印:

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