c#-4.0 - Weighted Directed Graph in QuickGraph Library

Question

Here is an example of my problem.

I would like to code this in C# in such a way so that I may interrogate the structure and find information such as:

• Total distance from A to B.
• Shortest distance from A to E (keeping in mind you can't go against the arrow's direction).

So I thought I would use an Adjacency List to model my graph, but then I thought this is a common thing, and started looking for libraries to help quicken the process (no need to re-invent the wheel .. etc.)

I came across this Library that was recommended a couple of time on various topics, but I am finding it real hard modelling my drawn graph above.

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