在List< Point>上运行Dijkstra的算法.在C#中 [英] Run Dijkstra's Algorithm on a List<Point> in C#

问题描述

我在C#中有一个Point类型的列表.我想在该点的列表上运行 Dijkstra的算法起始位置.

I have a list of Point types in C#. I want to run Dijkstra's algorithm on this list of points where the first entry in the list is the starting location.

是否可以使用现有的库来做到这一点?

Is there a way of doing this using an existing library?

如果不存在这样的库，有没有一种方法可以计算带有x和y坐标的两个点之间的距离.例如，计算点​​A(x坐标= 2，y坐标= 4)和点B((x坐标= 9，y坐标= 7)之间的距离.

If such library doesn't exist, is there a way of calculating the distance between two points with x and y coordinates. For example, calculate the distance between point A (x coordinate =2, y coordinate = 4) and point B ((x coordinate =9, y coordinate = 7).

我已经使用ZedGraph库来构建图形.

I have used the ZedGraph library to build the graph.

推荐答案

我认为您误会了Dijkstra算法的含义.

I think you misunderstood, what the Dijkstra algorithm stands for.

对于图中的给定源顶点(节点)，算法会找到该顶点与其他所有顶点之间成本最低的路径(即最短路径).

For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex.

根据两点的坐标，您需要的(我认为)是最短距离.

What you need (i think) the lowest distance between two points based on their coordinates.

两点之间的距离可以使用基本数学计算:

And the distance between two points can be counted using basic math:

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));

使用此知识，可以通过以下两个功能解决问题:

using this knowledge the problem could be solved with two functions like this:

返回p和r之间的距离:

Returns the distance between p and 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));
}

将最接近点的索引返回到points列表中第fromIndex个元素:

Returns the index of the closest point to the fromIndex th element of the points list:

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;
}

如果我误解了你，我真的很抱歉！

I'm really sorry, if i misunderstood you!

这篇关于在List< Point>上运行Dijkstra的算法.在C#中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！