c# - 在列表上运行 Dijkstra 算法在 C# 中

Question

我有一个 C# 中的点类型列表。我想在这个列表中的第一个条目是起始位置的点列表上运行Dijkstra 算法。

有没有办法使用现有的库来做到这一点？

如果这样的库不存在，有没有办法用 x 和 y 坐标计算两点之间的距离。例如，计算A点（x坐标=2，y坐标=4）和B点（（x坐标=9，y坐标=7）的距离。

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

Answer 1

我认为您误解了 Dijkstra 算法的含义。

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

您需要（我认为）基于坐标的两点之间的最短距离。

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

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

使用这些知识，可以使用如下两个函数来解决问题：

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

返回距离列表fromIndex第 th 个元素最近的点的索引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;
}

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