多点间最短路径 [英] Shortest route between multiple points

问题描述

我需要找到多个点之间的最短路径.假设我有这四点:

I need to find the shortest route between multipe points. Let's say that I have these four points:

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 的最短路线，首先要经过哪些点.

So, I want to find out which points to go past first, in order to get the shortest route, from startPoint to endPoint.

有人可以帮我吗?

更新:它必须经过pointsToGoPast 列表中的每个点.每条路线的成本是平均的.

Update: It has to go past each of the points in the pointsToGoPast list. The cost is even for each route.

推荐答案

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

You can do this by Dijkstra's Algorithm.

带有代码的示例项目

唯一需要改变的是项目中的权重，因为权重基于两点之间的距离.(所以你需要修改Location来存储一个Point和Connection来计算构造函数中的权重(距离).

The only thing that needs to change is the weights in the project, since the weight is based off of distance between the two points. (So you need to modify the Location to store a Point and the Connection to calculate the weight (distance) in the constructor.

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

这篇关于多点间最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！