1

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

在此处输入图像描述

我使用QuickGraph库(adjacencyGraph)对我的图进行建模。

我想找到一个最昂贵(最高)的距离/路径,例如 A > D > H > J 或 A > D > H > K

我将不胜感激任何帮助。谢谢。

4

2 回答 2

0

I found a solution. I multiply the cost of weights by -1 and I use Bellman Ford Shortest Path Algorithm to find the single source shorteset path (Ref : QuickGraph Shortest Path). This way I find the maximum path

Here is C# source code

    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}."); }
    }
于 2013-11-22T10:03:04.937 回答
0

除非您知道有关您拥有的图形的其他属性,并且假设没有循环,否则您可以进行简单的深度优先搜索(这可能比广度优先搜索更快,因为您只需要一个结果)。

于 2013-11-20T15:12:57.863 回答