c# - QuickGraph ライブラリで最も高価な (最高の) 距離/パスを見つける方法は?

Question

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

QuickGraphライブラリ (adjacencyGraph)を使用してグラフをモデル化します。

A > D > H > J または A > D > H > K など、最も高価な (最も高い) 距離/パスを見つけたい

助けていただければ幸いです。ありがとう。

Answer 1

解決策を見つけました。重みのコストに -1 を掛け、Bellman Ford Shortest Path Algorithm を使用して単一ソースの最短パスを見つけます (参照: QuickGraph Shortest Path )。このようにして、最大パスを見つけます

C#ソースコードはこちら

    public AdjacencyGraph<string, Edge<string>> Graph { get; private set; }
    public Dictionary<Edge<string>, double> EdgeCost { get; private set; }

    ......

    public void FindPath(string @from = "START", string @to = "END")
    {
        Func<Edge<string>, double> edgeCost = AlgorithmExtensions.GetIndexer(EdgeCost);
        // Positive or negative weights
        TryFunc<string, System.Collections.Generic.IEnumerable<Edge<string>>> tryGetPath = Graph.ShortestPathsBellmanFord(edgeCost, @from);

        IEnumerable<Edge<string>> path;
        if (tryGetPath(@to, out path))
        {
            Console.Write("Path found from {0} to {1}: {0}", @from, @to);
            foreach (var e in path) { Console.Write(" > {0}", e.Target); }
            Console.WriteLine();
        }
        else { Console.WriteLine("No path found from {0} to {1}."); }
    }