7

これが私の問題の例です。

ここに画像の説明を入力

構造を調べて次のような情報を見つけられるように、これを C# でコーディングしたいと思います。

  • AからBまでの合計距離。
  • AからEまでの最短距離(矢印の方向に逆らってはいけません)。

そのため、隣接リストを使用してグラフをモデル化しようと考えましたが、これは一般的なことだと思い、プロセスを高速化するのに役立つライブラリを探し始めました (車輪を再発明する必要はありません..など)。

さまざまなトピックで数回推奨されたこのライブラリに出くわしましたが、上記の描画されたグラフをモデル化するのは本当に難しいと感じています.

4

1 に答える 1

11

考えられる解決策は、グラフを としてモデル化し、コスト ディクショナリ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
于 2013-08-29T12:48:53.477 に答える