腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >结合Dijkstra算法和A*搜索？

问结合Dijkstra算法和A*搜索？
EN

Stack Overflow用户

提问于 2013-10-31 05:52:14

回答 2查看 208关注 0票数 0

有没有可能把Dijkstra算法和A* search结合起来？多么?

algorithm

dijkstra

a-star

回答 2

Stack Overflow用户

发布于 2013-10-31 06:18:24

Dijkstra算法只是A*搜索的一个特例，其中启发式函数为0。启发式算法越不准确，A*的行为就越像Dijkstra算法。实际上，你可能并不想组合它们，因为只要你有一个可接受的启发式A*，就永远不会比Dijkstra的算法扩展更多的节点。你只会削弱算法。

希望这能有所帮助！

票数 3

Stack Overflow用户

发布于 2013-10-31 08:57:42

但是你想要组合的problem?..why是什么呢？A*搜索有一个非常昂贵的内存请求，你可以使用迭代加深A*。对于Dijkstra算法，您可以使用二进制最小堆来实现最低优先级队列

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/19699329

复制

Dijkstra算法和Floyed算法「建议收藏」

编程算法

在非网图中，最短路径是指两顶点之间经历的边数最少的路径。在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。

全栈程序员站长

2022/07/04

4960

Dijkstra算法

编程算法

nx.info: [1, 2, 3, 4, 6, 7, 8, 9, 10, 11] 顶点 v1 到顶点 v11 的最短加权路径: [1, 2, 3, 7, 10, 9, 11] 顶点 v1 到顶点 v11 的最短加权路径长度: 9

裴来凡

2022/05/29

4030

Dijkstra算法

编程算法 javascript 其他

Dijkstra算法使用了广度优先搜索解决赋权有向图（或无向图）的单源最短路径问题。

mwangblog

2019/05/16

1.1K0

Dijkstra算法

java https 网络安全编程算法

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其它全部节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但因为它遍历计算的节点非常多，所以效率低。

全栈程序员站长

2021/12/05

4510

【图】Dijkstra算法

编程算法 ios

正文之前好久没弄C++了，上学期颓废了半学期，这学期开学就搞课程设计快疯了。待会要考试CSP，所以弄点代码储备，待会到了考场说不定能省点功夫！正文 #include<iostream> usin

用户1687088

2018/07/24

1K0

最短路径—大话Dijkstra算法和Floyd算法

编程算法

Dijkstra算法算法描述 1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就

互联网金融打杂

2018/04/03

2.1K0

dijkstra算法python实现

算法

MAX_value = 999999 def dijkstra(graph, s): # 判断图是否为空，如果为空直接退出 if graph is None: return None dist = [MAX_value]*len(graph) dist[s] = 0 S = [] Q = [i for i in range(len(graph))] dist_init = [i for i in graph[s]] whil

py3study

2020/01/06

8060

dijkstra算法原理是什么？dijkstra算法的缺点是什么？

编程算法

dijkstra算法也被称为狄克斯特拉算法，是由一个名为狄克斯特拉的荷兰科学家提出的，这种算法是计算从一个顶点到其他各个顶点的最短路径，虽然看上去很抽象，但是在实际生活中应用非常广泛，比如在网络中寻找路由器的最短路径就是通过该种算法实现的。那么dijkstra算法原理是什么？dijkstra算法的缺点是什么？

用户8739990

2021/06/25

8.7K0

Dijkstra算法例子

node.js

%d 输出向量路径长度，若t==[]，则返回从起点到所有节点的路径长度

mwangblog

2019/05/16

9160

图论--Dijkstra算法总结

其他 https 网络安全

1.BFS转换Dijkstra：对于一些路径的的问题及一些特殊的搜索题目，如果数据量很多但是处理边的复杂程度可以接受，就是说我们可以通过操作将原来要搜索的问题转化为Dijkstra能做的问题，这样可以提高效率，虽然介于BFS与Dijkstra之间有着A*，但是A*的题目我目前就看到了一类，第K短路，常用的还是转换。举个例子：在一个城堡中，有机关陷阱并且告知了其坐标，设城堡为一个二维平面，若这个二维有10000点，BFS最坏的情况是O（V^2）那么可能会超时，那么我们考虑，将每个点的作为节点建图，若有机关则他与上下左右都不连通，其他的每个点建立四联通边，那么时间复杂度为O(4*V),再加上Dijkstra为O（4*V+VlogV）可以将其解出，这个例子可能不太恰当，但是在这里给出解题的思想，BFS与Dijkstra同是单源最短路是可以转化的。

风骨散人Chiam

2020/10/28

7080

图算法|Dijkstra算法python实现

编程算法 python

01 — Dijkstra算法的理论部分关于Dijkstra算法的原理部分，请参考之前的推送：图算法|Dijkstra最短路径算法 Dijkstra算法总结如下： 1. 此算法是计算从入度为0的起始点开始的单源最短路径算法，它能计算从源点到图中任何一点的最短路径，假定起始点为A 2. 选取一个中心点center，是S集合中的最后一个元素，注意起始点到这个点的最短距离已经计算出来，并存储在dist字典中了。 3. 因为已经求出了从A->center的最短路径，所以每次迭代只需要找出center->{有关

double

2018/04/02

3.3K0

最短路径：dijkstra算法

dijkstra

#include <iostream> using namespace std; #define N 510 #define INF 0x3f3f3f3 int g[N][N]; int dist[N]; bool st[N]; int n, m; //返回值为1到n的路径长度 int dijkstra() { memset(dist, INF, sizeof dist); dist[1] = 0;//初始路径长度为0 自己到自己 for(int i=0; i<n; ++i) {

lexingsen

2022/02/24

4.2K0

使用 Go 实现 Dijkstra 算法

go dijkstra key 队列算法

Dijkstra 算法是由荷兰计算机科学家 Edsger W. Dijkstra 在 1956 年提出的。这个算法可以找到从起始点到图中所有其他点的最短路径。算法的主要思想是：每次从未处理的顶点中选取一个与起始点距离最短的顶点，然后更新所有与该顶点相邻的顶点的最短路径。

运维开发王义杰

2023/10/23

3440

单源最短路径dijkstra算法_dijkstra是谁

java https 网络安全

酋长说：”嗯，如果你能够替我弄到大祭司的皮袄，我可以只要 8000 金币。如果你能够弄来他的水晶球，那么只要 5000 金币就行了。”

全栈程序员站长

2022/09/22

7310

ACM算法竞赛——朴素dijkstra算法（模板）

腾讯微信算法大赛

int g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路是否已经确定 // 求1号点到n号点的最短路，如果不存在则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n - 1; i ++ ) { int t = -1;

战士小小白

2022/05/16

4520

[图]最短路径-Dijkstra算法

编程算法 https 网络安全

2.BFS可能会是Dijkstra算法的实质，BFS使用的是队列进行操作，而Dijkstra采用的是优先队列。

王荣胜

2020/03/13

7K0

漫画：Dijkstra 算法的优化

编程算法

在上一篇漫画中，小灰介绍了单源最短路径算法 Dijkstra，没看过的小伙伴可以看下：

小灰

2020/04/22

5920

Dijkstra 算法的 python 实现

python

离散课上图论的时候讲了理论知识，但是还没实践过，于是拿python写了一下，顺便做个笔记防止忘记。

赤道企鹅

2022/08/01

7440

点击加载更多

相似问题

Dijkstra算法和循环

Dijkstra算法和函数

Dijkstra算法

341

Dijkstra算法

Dijkstra算法有双向搜索的实现吗？

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问结合Dijkstra算法和A*搜索？
EN

回答 2

Stack Overflow用户

Stack Overflow用户

Dijkstra算法和循环

Dijkstra算法和函数

Dijkstra算法

Dijkstra算法

Dijkstra算法有双向搜索的实现吗？

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问结合Dijkstra算法和A*搜索？EN

回答 2

Stack Overflow用户

Stack Overflow用户

Dijkstra算法和循环

Dijkstra算法和函数

Dijkstra算法

Dijkstra算法

Dijkstra算法有双向搜索的实现吗？

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问结合Dijkstra算法和A*搜索？
EN