标签: shortest-path

我做了一些研究,我似乎错过了这个算法的一小部分.我明白了一个广度优先搜索是如何工作的,但我不明白它究竟是如何让我到一个特定的路径,而不是仅仅告诉我,每个单独的节点可以走了.我想解释我困惑的最简单方法是提供一个例子:

例如,假设我有一个这样的图形:

我的目标是从A到E(所有边缘都没有加权).

我从A开始,因为那是我的起源.我排队A,然后立即将A排队并探索它.这产生B和D,因为A连接到B和D.因此我将B和D排队.

我将B排队并探索它,并发现它导致A(已经探索过)和C,所以我排队C.然后我排队D,并发现它导致E,我的目标.然后我将C排队,并发现它也导致E,我的目标.

我逻辑上知道最快的路径是A-> D-> E,但我不确定广度优先搜索有多精确 - 我应该如何记录路径,这样当我完成时,我可以分析结果并查看最短的路径是A-> D-> E？

另外,请注意我实际上并没有使用树,因此没有"父"节点,只有子节点.

有人可以告诉我为什么Dijkstra的单源最短路径算法假设边缘必须是非负的.

我说的只是边缘而不是负重量周期.

我试图理解为什么Dijkstra的算法不适用于负权重.阅读最短路径上的示例,我试图找出以下场景:

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

来自网站:

假设边缘全部从左向右指向,如果我们从A开始,Dijkstra算法将选择最小化d(A,A)+长度(边缘)的边(A,x),即(A,B).然后设置d(A,B)= 2并选择另一个边(y,C),使d(A,y)+ d(y,C)最小化; 唯一的选择是(A,C),它设置d(A,C)= 3.但它从未找到从A到B的最短路径,通过C,总长度为1.

我无法理解为什么使用Dijkstra的以下实现,d [B]将不会更新为1(当算法到达顶点C时,它将在B上运行放松,看到d [B]等于2,因此更新它的价值1).

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ? Ø
   Q ? V[G]//priority queue by d[v]
   while Q ? Ø do
      u ? Extract-Min(Q)
      S ? S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v ? V(G)
      d[v] ? ?
      ?[v] …

我一直在为即将到来的编程竞赛练习,我偶然发现了一个我完全不知所措的问题.然而,我觉得这是一个我现在应该学习的概念,而不是交叉指责它永远不会出现.

基本上,它涉及棋盘上的骑士棋子.您将获得两个输入:起始位置和结束位置.目标是计算并打印骑士可以到达目标位置的最短路径.

我从来没有处理过最短路径的事情,我甚至不知道从哪里开始.我采用什么逻辑来解决这个问题？

PS如果它有任何相关性,他们希望你补充骑士的正常动作,同时允许它移动到由骑士可以做的(潜在的)八个动作所形成的方形的四个角,因为方形的中心是骑士的位置.

我正在OpenStreetMap地图上写一个快递/物流模拟,并且已经意识到如下图所示的基本A*算法对于大型地图(如大伦敦)来说不够快.

绿色节点对应于放置在开放集/优先级队列中的绿色节点,并且由于数量巨大(整个地图大约为1-2百万),需要5秒左右才能找到所示的路线.不幸的是,每条路线100毫秒是我的绝对限制.

目前,节点存储在邻接列表和空间100×100 2D阵列中.

我正在寻找可以在预处理时间,空间和路线最佳性能之间进行权衡的方法,以便更快地进行查询.根据剖析器,启发式成本的直线Haversine公式是最昂贵的函数 - 我尽可能地优化了我的基本A*.

例如,我在想是否从2D阵列的每个象限中选择一个任意节点X并在每个象限之间运行A*,我可以将路径存储到磁盘以供后续模拟.查询时,我只能在象限中​​运行A*搜索,以便在预先计算的路径和X之间进行搜索.

是否有我上面所描述的更精致的版本,或者我应该追求的另一种方法.非常感谢!

为了记录,这里有一些基准测试结果,用于任意加权启发式成本并计算10对随机选取的节点之间的路径:

Weight // AvgDist% // Time (ms)
1       1       1461.2
1.05    1       1327.2
1.1     1       900.7
1.2     1.019658848     196.4
1.3     1.027619169     53.6
1.4     1.044714394     33.6
1.5     1.063963413     25.5
1.6     1.071694171     24.1
1.7     1.084093229     24.3
1.8     1.092208509     22
1.9     1.109188175     22.5
2       1.122856792     18.2
2.2     1.131574742     16.9
2.4     1.139104895     15.4
2.6     1.140021962     16
2.8     1.14088128      15.5
3       1.156303676     16
4       1.20256964      13
5       1.19610861      12.9

令人惊讶的是,将系数增加到1.1几乎将执行时间减半,同时保持相同的路线.

我知道有很多算法可用于计算图形或网格中两点之间的最短路径,如广度优先,全对(Floyd's),Dijkstra's.

但是,正如我所注意到的,所有这些算法都计算出该图或网格中的所有路径,而不仅仅是我们感兴趣的两点之间的路径.

我的问题是: 如果我有一个网格,即一个二维数组,我有兴趣计算两点之间的最短路径,比如P1和P2,如果我可以在网格上移动的方式有限制(例如,只对角,或只对角和向上等),什么算法可以计算这个？

请注意,如果您有答案,我希望您发布算法的名称而不是算法本身(当然,如果您也发布算法,则更好); 例如,无论是Dijkstra的算法,还是Floyd的算法,或者其他什么.

请帮助我,我几个月来一直在考虑这个问题!

好吧我们在TOPCODER.COM上发现这个算法在网格中你只能移动(对角线和向上)但我无法理解这是什么算法,任何人都知道？

#include<iostream>
#include <cmath>

using namespace std;




inline int Calc(int x,int y)

{



if(abs(x)>=abs(y)) return abs(x);
int z=(abs(x)+abs(y))/2;
return z+abs(abs(x)-z);
 }

class SliverDistance
{


    public:
int minSteps(int x1,int y1, int x2, int y2)
{
    int ret=0;
    if(((x1+y1)&1)!=((x2+y2)&1))y1++,ret++;
    return ret+Calc(x2-x1,y2-y1);
}
};

经过大量的谷歌搜索后,我发现大多数消息来源称Dijkstra算法比Bellman-Ford算法"更有效".但在什么情况下Bellman-Ford算法比Dijkstra算法更好？

我知道"更好"是一个广泛的陈述,所以具体来说,我的意思是速度和空间,如果适用.当然,在某些情况下,贝尔曼 - 福特方法比Dijkstra方法更好.

任何人都可以告诉我Dijkstra和Prim的算法之间的区别吗？我知道每个算法的作用.但他们看起来和我一样.Dijkstra算法存储最小成本边的总和,而Prim算法存储最多一个最小成本边.这不一样吗？

我需要帮助找到未加权无向图中两个节点之间的所有最短路径.

我能够找到使用BFS的最短路径之一,但到目前为止,我迷失了如何找到并打印出所有这些路径.

我可以使用算法/伪代码的任何想法吗？

我正在阅读Dijkstra的算法和Floyd-Warshall算法.据我所知,Dijkstra找到了从一个节点到所有其他节点的最佳路径,Floyd-Warshall找到了所有节点配对的最佳路径.

我的问题是,如果我在每个节点上运行它,Dijkstra算法比Floyd更有效,以便找到所有配对之间的最佳路径.

Dijkstra的运行时间是O(E + VlogV),其中Floyd是O(V ³).如果Dijkstra失败了,在这种情况下它的运行时间是什么？谢谢!