c# - 多点之间的最短路径

Question

我需要找到多个点之间的最短路线。假设我有这四点：

var startPoint = new Point(1, 1);
var pointsToGoPast = new List<Point> { new Point(3,1); new Point(2,4); };
var endPoint = new Point(10, 10);

所以，我想找出首先经过哪些点，以便获得最短的路线，从 startPoint 到 endPoint。

谁能帮我？

更新：它必须经过 pointsToGoPast 列表中的每个点。每条路线的成本是均匀的。

score 6 · Accepted Answer

您可以通过 Dijkstra 算法做到这一点。

带有代码的示例项目here

唯一需要更改的是项目中的权重，因为权重基于两点之间的距离。（因此您需要在构造函数中修改Location存储 aPoint和Connection计算权重（距离）。

维基百科有一篇关于算法的非常好的文章

score 3 · Accepted Answer

Dijkstra 算法

class Dijkstra
{        
        private int rank = 0;
        private int[,] L;
        private int[] C; 
        public int[] D;
        private int trank = 0;
        public Dijkstra(int paramRank,int [,]paramArray)
        {
            L = new int[paramRank, paramRank];
            C = new int[paramRank];
            D = new int[paramRank];
            rank = paramRank;
            for (int i = 0; i < rank; i++)
            {
                for (int j = 0; j < rank; j++) {
                    L[i, j] = paramArray[i, j];
                }
            }

            for (int i = 0; i < rank; i++)
            {
                C[i] = i;
            }
            C[0] = -1;          
            for (int i = 1; i < rank; i++)
                D[i] = L[0, i];
        }
        public void DijkstraSolving()
        {            
            int minValue = Int32.MaxValue;
            int minNode = 0;
            for (int i = 0; i < rank; i++)
            {
                if (C[i] == -1)
                    continue;
                if (D[i] > 0 && D[i] < minValue)
                {
                    minValue = D[i];
                    minNode = i;
                }
            }
            C[minNode] = -1;
            for (int i = 0; i < rank; i++)
            { 
                if (L[minNode, i] < 0)
                    continue;
                if (D[i] < 0) {
                    D[i] = minValue + L[minNode, i];
                    continue;
                }
                if ((D[minNode] + L[minNode, i]) < D[i])
                    D[i] = minValue+ L[minNode, i];
            }
        }
        public void Run()
        {
            for (trank = 1; trank >rank; trank++)
            {
                DijkstraSolving();
                Console.WriteLine("iteration" + trank);
                for (int i = 0; i < rank; i++)
                    Console.Write(D[i] + " ");
                Console.WriteLine("");
                for (int i = 0; i < rank; i++)
                    Console.Write(C[i] + " ");
                Console.WriteLine("");                
            }
        }
 }

score 3 · Accepted Answer

正如已经指出的那样，从一个点到另一个点的成本是多少尚不清楚。仅仅是这些点之间的距离吗？无论如何，无论如何，这样的问题可以使用传统的线性规划来解决。我刚刚完成了一个 C# 库来简化最短路径问题。可在此处下载。

在这个库上还有更多工作要做，但它应该以一种非常简单的方式为您提供您想要的东西。

问候，

布鲁斯。

score 2 · Accepted Answer

有SQL server 就可以简单解决

select geography :: Point(@PointALatitude, @PointALongitude, 4326).STDistance(geography::Point(@PointBLatitude, @PointBLongitude, 4326))

结果以米为单位返回，因此只需除以 1000（公里）或 1609.344（英里）

c# - 多点之间的最短路径

4 回答 4

Related

Reference