0

C# の Point 型のリストがあります。リストの最初のエントリが開始位置であるこのポイントのリストで、ダイクストラのアルゴリズムを実行したいと思います。

既存のライブラリを使用してこれを行う方法はありますか?

そのようなライブラリが存在しない場合、x 座標と y 座標を持つ 2 点間の距離を計算する方法はありますか。たとえば、点 A (x 座標 = 2、y 座標 = 4) と点 B ((x 座標 = 9、y 座標 = 7)) の間の距離を計算します。

ZedGraph ライブラリを使用してグラフを作成しました。

4

1 に答える 1

0

ダイクストラアルゴリズムが何を表しているのか、あなたは誤解していると思います。

グラフ内の特定のソース頂点 (ノード) について、アルゴリズムは、その頂点と他のすべての頂点との間の最小コストのパス (つまり、最短パス) を見つけます。

必要なのは (私が思うに) 座標に基づく 2 点間の最小距離です。

2 点間の距離は、基本的な数学を使用して数えることができます。

Point p = new Point(4, 5);
Point r = new Point(10, 2);

double distance = Math.Sqrt(Math.Pow(p.X - r.X, 2) + Math.Pow(p.Y - r.Y, 2));

この知識を使用すると、次のような 2 つの関数で問題を解決できます。

pとの間の距離を返しますr:

static double distance(Point p, Point r)
{
     return Math.Sqrt(Math.Pow(p.X - r.X, 2) + Math.Pow(p.Y - r.Y, 2));
}

リストのfromIndexth 要素に最も近いポイントのインデックスを返します。points

static int closestPoint(List<Point> points, int fromIndex)
{
    Point start = points[fromIndex];
    int resultIndex = 0;

    for (int i = 1; i < points.Count; i++)
    {
        if (fromIndex == i) 
            continue;

        Point current = points[i];

        if (distance(start, current) < distance(start, points[resultIndex]))
            resultIndex = i;
    }

    return resultIndex;
}

私があなたを誤解していたら、本当にごめんなさい！

于 2012-09-02T18:43:11.960 に答える