“弗洛伊德-沃尔”算法“和”Dijkstra的算法“”之间有什么区别,哪种算法是图中最短路径的最佳选择?
我需要计算网络中所有对之间的最短路径,并将结果保存到一个数组中,如下所示:
**A B C D E**
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0
我正在尝试用C++创建一个简单的基于网格的游戏。寻路是其中必要的一部分。我一直在找,但并不完全是我要找的。
规则很简单。有一张地图。大小一般不超过100 x 100平铺。1是地砖,0是墙。不允许对角线移动,因此每个网格只有4个方向。然而,大多数情况下都有不止一个目标。我想找一条最近的路。记住,我们不能只计算距离公式,哪一个是最近的。距离短的目标可以走更远的路,因为有墙。我认为使用一种已知的算法,并为每个目标重复,这不是一个好主意,因为它会变慢。
你的意见呢?我该怎么办?
假设我有一个带有N顶点和M边的图M。每一条边都有它的长度和时间(例如,以分钟为单位),通过该边所需的时间。我需要在图中找到顶点1和N之间的最短路径,这是在T分钟时间内执行的。因为时间是更有价值的资源,我们关心的是在时间上遍历图,只有在最短的时间内,我才决定使用Dijkstra的算法,对此我考虑了每条边的时间作为它的权重。我添加了一个向量来存储持续时间。因此,该算法返回最少的时间,而不是最小的长度。一位朋友建议在我的代码中添加以下内容:
int answer(int T) {
int l = 1;
int r = M; // a very big number
int a