如何设置目标顶点在QuickGraph Dijkstra算法或A * [英] How to set target vertex in QuickGraph Dijkstra or A*

问题描述

我使用QuickGraph 3.6版，我发现功能SetRootVertex，但没有SetTagretVertex。我需要这个，因为我在巨大的图形搜索短的路径，这将加快程序很多。

I am using QuickGraph version 3.6 and I found function SetRootVertex, but no SetTagretVertex. I need this because I am searching short paths in huge graph and this would speed up program a lot.

Clases问题是DijkstraShortestPathAlgorithm和AStarShortestPathAlgorithm。

Clases in question are DijkstraShortestPathAlgorithm and AStarShortestPathAlgorithm.

推荐答案

我不认为有一种方法可以不借助事件。

I don't think there is a way to this without using events.

您可以包装所需的代码在一个扩展方法，澄清事情，例如：

You could wrap the necessary code in one extension method, making things clear, e.g.:

public static class Extensions
{
    class AStarWrapper<TVertex, TEdge>
    where TEdge : IEdge<TVertex>
    {
        private TVertex target;
        private AStarShortestPathAlgorithm<TVertex, TEdge> innerAlgorithm;
        public AStarWrapper(AStarShortestPathAlgorithm<TVertex, TEdge> innerAlgo, TVertex root, TVertex target)
        {
            innerAlgorithm = innerAlgo;
            this.innerAlgorithm.SetRootVertex(root);
            this.target = target;
            this.innerAlgorithm.FinishVertex += new VertexAction<TVertex>(innerAlgorithm_FinishVertex);
        }
        void innerAlgorithm_FinishVertex(TVertex vertex)
        {
            if (object.Equals(vertex, target))
                this.innerAlgorithm.Abort();
        }
        public double Compute()
        {
            this.innerAlgorithm.Compute();
            return this.innerAlgorithm.Distances[target];
        }
    }

    public static double ComputeDistanceBetween<TVertex, TEdge>(this AStarShortestPathAlgorithm<TVertex, TEdge> algo, TVertex start, TVertex end)
        where TEdge : IEdge<TVertex>
    {
        var wrap = new AStarWrapper<TVertex, TEdge>(algo, start, end);
        return wrap.Compute();
    }
}

用法：

var g = new BidirectionalGraph<int, IEdge<int>>();

g.AddVerticesAndEdge(new Edge<int>(1, 2));
g.AddVerticesAndEdge(new Edge<int>(2, 3));
g.AddVerticesAndEdge(new Edge<int>(3, 4));
g.AddVerticesAndEdge(new Edge<int>(2, 4));

var astar =new AStarShortestPathAlgorithm<int,IEdge<int>>(g, x => 1.0, x => 0.0);
var dist = astar.ComputeDistanceBetween(2, 4);

这篇关于如何设置目标顶点在QuickGraph Dijkstra算法或A *的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！