-
15 votesanswersviews
有效地找到大图中的最短路径
我正在寻找一种方法来实时找到巨大图形中节点之间的最短路径 . 它有数十万个顶点和数百万个边 . 我知道之前已经问过这个问题，我想答案是使用广度优先搜索，但我更感兴趣的是知道可以用什么软件来实现它 . 例如，如果已经存在用于在无向图中执行bfs的库（使用python绑定！），那将是完全完美的 . -
0 votesanswersviews
R：计算两个顶点之间的单个最短路径
目前，我正在开展一个涉及纽约出租车数据的项目，在这个项目中，我可以获得一个人在网络中被接送的地方 . 我正在使用 ESRI shapefile ，我可以使用 shp2graph 包将其作为 igraph 对象加载到R中;我需要利用Dijkstra算法（或类似的最短路径算法）来找到两个给定顶点之间的单个最短路径 . 我认为 igraph 包的 get.shortest.paths() 方法将是我... -
1 votesanswersviews
修改的最短路径算法，禁止路径
我们提供了图G =（V，E），其中每个边与一些正权重（W [i]> 0）相关联 . 如果我们遵循以下条件，我们被要求找到从A到B的最短路径： 我们也有一些禁止的路径，比如说x . 目标是最短路径不应包含任何禁止路径作为其子路径 . 例如：考虑一个图G，有4个顶点和5个边（1,2,1），（2,1,1），（1,4,5），（1,3,1.5），（3,4， 1） . 这里，括号中的第三个实体表示“u”... -
0 votesanswersviews
一种特定的PathFinding方法
我正在使用Unity，使用C＃进行一个非常简单的项目 . 我坚持使用pathFinding . 我看着Dikjstra 's and A* for reference, but for some reason I still can' t采用它们来处理我的情况 . 我想我的大脑 :=while(1); 这是想法： 从文本文件中我导入一个“ Map ”，其中每个“*”表示Wall，以及每个“”wal... -
1 votesanswersviews
使用Dijkstra算法在网格上进行寻路[关闭]
这次Dijkstra的路径发现再次出现问题 我在不同的网站上阅读过Dijkstra及其应用程序 . 它主要针对Graph进行了解释，并找出了源节点中所有节点的最短路径 . 我无法弄清楚如何使用Dijkstra在网格上寻找路径，如Wikipedia picture所述 . 因为在网格上我们有一个目的地，我们必须从源头找出它的最短距离 . 我无法将它与Dijkstra的图表联系起来 . 没有瓷砖被标记... -
2 votesanswersviews
Dijsktra图，最短路径
我的图表有问题 . 我的图表看起来像这样： 真正的问题是：我想在两点之间找到具有最少量“转弯”的路径 . 这是一个例子： 在这张图中我绘制了一个简单的3x3图形，红点和蓝点之间的最短路径是绿线，因为它只有一个转弯，而粉红线有3转 . 我想相应地权衡图形的边缘，然后使用Dijsktra的算法来找到合适的路径 -
92 votesanswersviews
如果广度优先搜索（BFS）可以更快地做同样的事情，为什么要使用Dijkstra的算法？
两者都可用于从单一来源找到最短路径 . BFS在 O(E+V) 中运行，而Dijkstra在 O((V+E)*log(V)) 中运行 . 另外，我见过Dijkstra在路由协议中使用了很多 . 因此，如果BFS可以更快地做同样的事情，为什么要使用Dijkstra的算法呢？ -
1 votesanswersviews
Java中的边缘不相交最短对算法？
我试图找到 shortest pair of edge-disjoint paths between a given pair of vertices ，我正在关注这个algorithm，一般来说是 Suurballe's algorithm 我猜 . 这是算法： 为给定的顶点对运行最短路径算法（我正在使用Dijkstra算法） 用指向源顶点的单个弧替换最短路径的每条边（相当于两个相反方向... -
0 votesanswersviews
通过某些边缘的最短路径算法
我需要在图表中找到最短路径，该路径至少经过标记为“必须通过”的一条边 . 有任何想法吗？可以修改Dijkstra的算法以实现这一目标吗？ 谢谢 . -
2 votesanswersviews
通过某些已定义节点的最短路径
在有向图中，找到从s到t的最短路径，使得路径通过V的某个子集，让我们称它们为死亡节点 . 算法给出一个数n，当从s到t遍历时，该路径不能超过n个死亡节点 . 她找到最短路径的最佳方法是什么？我正在削弱Dijkstra，但是如何确保我们不会超过n个节点？请帮我调整Dijkstra's以包含这个条件 . -
0 votesanswersviews
找到最短路径，在图表中恰好包含一个负边缘
我得到了一个带有权函数和顶点s的有向图 . 我的目标是找到任何其他顶点v，从s到v的最短路径，它经过恰好一个负边缘 . 算法的时间复杂度应为O（| E | | V | * log | V |），所以我猜需要以某种方式使用Dijkstra算法 . 我猜我需要将我给定的图形以某种方式转换为具有非负权重的新图形，该图形中从s到v的最短路径将等于给定图形中所需的最短路径...或者我可能需要以某种方式修改D... -
2 votesanswersviews
在具有两个负边的图中找到从给定节点s到V中的所有节点的最短路径距离
我对此有一个后续问题：Finding shortest path distances in a graph containing at most two negative edges Ranveer的解决方案看起来很棒，但它不够快，因为我需要O（| E | | V | * log | V |）快速算法 . 我猜Dukeling的解决方案效果很好 . 它有意义，它在Dijkstra算法的相同运行时间... -
3 votesanswersviews
在2D整数数组Java中查找最短路径
我正在进行蛇形游戏，其中蛇穿过2D int数组作为其地形 . 存储在2D数组中的值表示跨越所需的时间（以秒为单位） . 例如， int[][] MAP = { { 1, 1, 1, 2, 2 }, { 1, 2, 2, 2, 2 }, { 3, 2, 2, 3, 1 }, { 1, 1, 3, 2, 1 }, { 1, 1, 3, 2, 1 } }; ... -
7 votesanswersviews
Dijkstra的负权重算法
好的，首先我知道Dijkstra不适用于负重量，我们可以使用Bellman-ford代替它 . 但是在一个问题中，我给它说明所有边都有从0到1的权重（不包括0和1） . 而路径的成本实际上就是产品 . 所以我在想的只是记录日志 . 现在所有的边都是负的 . 现在我知道Dijkstra不会用于负权重，但在这种情况下所有边缘都是负数，所以我们不能做一些事情让Dijkstra工作 . 我将所有权重乘以-... -
0 votesanswersviews
Dijkstra的算法 - 为什么每次都提取具有最小优先级的顶点？
我正在学习Dijkstra的算法以找到最短路径 . 我注意到有一个优先级队列来帮助提取顶点集中具有最低优先级的顶点 . 如果我是 pick a vertex regardless of priority ，而不是优先级最低的算法，那么算法是否仍然有效？ If yes, what about the time complexity? 来自维基百科的原始Dijkstra算法如下： function ... -
3 votesanswersviews
两点之间网格中的最短路径 . grab 了
我有这个问题，我必须通过向右或向下移动找到NxM网格中从A点（总是左上角）到B点（总是右下角）的最短路径 . 听起来很简单，嗯？好吧，这里有一个问题：我现在只能移动我正坐在的瓷砖上显示的数字 . 让我说明一下： 2 5 1 2 9 2 5 3 3 3 1 1 4 8 2 7 在这个4x4网格中，最短路径将需要3个步骤，从左上角2个节点向下步行到3个，从那里3个节点从右到1，然后从1个节点向下到达... -
0 votesanswersviews
Tinkerpop / TinkerGraph快速方法
我创建了一个巨大的Tinkergraph（就顶点/边缘而言）我希望以最快的方式在其上应用方法 . 目前我正在使用带有tinkerpop依赖的java . 我的问题是： 给定两个顶点（gremlin）如何以最快的方式添加边缘而不覆盖先前的边缘 . 我希望添加具有权重属性的边，因此给定边e，如果边存在，那么我只将其权重增加1，如果不存在则从1开始 . 给定顶点我只希望将它添加到图形中（如果... -
2 votesanswersviews
boost :: dijkstra_shortest_paths覆盖内部图形权重？
我正在使用Boost Graph Library来存储具有 double 边缘权重和 double 顶点权重的无向图 . 在我的代码中的几个地方，我需要应用Dijkstra的算法来搜索最短路径 . 这很有效，直到我决定用我自己的权重暂时覆盖存储的边权重（仅暂时，不应修改图权重） . 我的代码基本上是这样的： // Initial typedefs typedef boost::propert... -
0 votesanswersviews
多目标的最短路径
我遇到了一个具有以下约束条件的送货员问题，我想听听您应该创建一个新算法的现有算法，或者希望只修改现有算法 . 具有偶数顶点的加权边的顶点图，具有顶点对，并且每个顶点具有15的权重 - 拾取和丢弃包需要时间 . 一对顶点包含“拾取位置”和“下降位置”Pn和Dn . 送货员可以在图表的任何地方 . 送货员必须到一对的Pn顶点 - “拾取位置” - 然后是Dn . 顶点具有到所有其他顶点的加权边 . ... -
-2 votesanswersviews
是否有算法来查找每个节点与所有其他节点的距离[重复]
这个问题在这里已有答案： Fastest implementation for All-pairs shortest paths problem? 5个答案 我想从所有其他节点获得所有节点的距离 . 例如，如果我有4个节点，那么我想要路径距离 （1,2），（1,3），（1,4），（2,3），（2,4），（3,4） 即所有可能的对 注意：每个节点都有一个来自其他每个节点的路径 . 我的方法：我考... -
3 votesanswersviews
消除两个顶点之间的所有最短路径
给定有向图 G=(V,E) ，两个顶点 s ， t 和两个权重函数 w1 ， w2 ，我需要在 s 之间的 s 到 t 之间的所有最短路径中找到 s 到 t 的最短路径 . 首先，我怎样才能找到两个顶点 s 和 t 之间的所有最短路径？ Dijkstra的算法帮助我们找到从顶点到每个其他可访问顶点的最短路径，是否可以修改它以获得两个顶点之间的所有最短路径？ -
-1 votesanswersviews
最短路径算法成本计算
所以问题是这样的：给出有向图G =（V，E）和权重函数wt：E-> R.您还会得到两个不同的节点s，t∈V写一个算法，该算法标记每个节点v，使得v位于从s到t的最短路径上 . 也就是说，为每个节点引入一个布尔字段v . 你的算法应该 Build 后置条件：∀v∈V：v.on≡（∃p：shpath（p，s，t）∩沿（v，p））我们定义shpath（p，s，t）=路径（p，s，t）∩wt（p）=... -
3 votesanswersviews
Dijkstra的算法具有最小边缘
首先让我们定义Dijkstra算法：Dijkstra算法在具有非负边权重的有向图中找到单源最短路径 .如果我有一个源S和目标TI可以使用 Dijkstra 算法找到这两个顶点之间的最短路径但是这里有问题我想找到这两个顶点之间的最短路径，这两个顶点之间的边数不超过K .第一部分是Dijkstra算法，但第二部分是 BFS 算法，因为我们可以用 BFS 算法在无加权图中找到最短路径 .所以我想知道是... -
17 votesanswersviews
找到通过一些任意节点序列的最短路径？
在this earlier question中，OP询问如何在图中找到从u到v的最短路径，并且还通过某个节点w . 接受的答案非常好，就是运行Dijkstra 's algorithm twice - once to get from u to w and once to get from w to v. This has time complexity equal to two calls to... -
4 votesanswersviews
用Dijkstra算法找到哈密顿路径？
Dijkstra算法可以找到从单个源顶点到所有其他顶点的所有最短路径，这样路径就可以访问无向和对称图形中的所有顶点一次并且恰好一次吗？对称图有更快的算法吗？ -
1 votesanswersviews
在包含至多两个负边的图中查找最短路径距离
我得到了一个有向图，其中每个边都有成本 . 利用图中最多有两个负边的事实，我的目标是找到从给定节点到V中所有节点的最短路径距离 . 算法的时间复杂度应该是 O(|E| + |V|*log|V|) ，所以我认为我需要应用Dijkstra的算法 . 我猜我需要将我的给定图形以某种方式转换为具有非负权重的新图形，该图形中从s到v的最短路径将等于给定图形中所需的最短路径...或者我可能需要修改Dijkst... -
103 votesanswersviews
使用Dijkstra算法的负权重
我试图理解为什么Dijkstra的算法不适用于负权重 . 阅读Shortest Paths上的示例，我试图找出以下场景： 2 A-------B \ / 3 \ / -2 \ / C 来自网站： 假设边缘全部从左向右指向，如果我们从A开始，Dijkstra算法将选择最小化d（A，A）长度（边缘）的边（A，x），即（A，B） . 然后设置d（A，B）= 2并选择另一个... -
0 votesanswersviews
如果我们有能力克服MOST 1障碍，那么计算从开始到结束的最短路径
我们以2D整数矩阵的形式给出了一个迷宫;其中0是可通空间，1是墙 . 起始位置始终是： array[0][0] 并且结尾将始终为： array[HEIGHT -1][WIDTH-1] 唯一可能的移动是向上，向下，向右或向左 . 我想找到从开始到结束的最短路径，考虑到我们最多可以克服迷宫内的一面墙 . 我开始创建一个Maze类和一个Vertex类 . 我的第一个想法是使用BFS，但是，我最近意识... -
6 votesanswersviews
提升's Dijkstra' s算法教程
我很难弄清楚如何使用Boost的Dijkstra算法 . 我已经查看了他们的示例和文档，但我仍然无法理解如何使用它 . [Boost的文档：http：//www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html] [Dijkstra的例子：http：//www.boost.org/doc/libs/1_36_... -
5 votesanswersviews
Boost :: graph Dijkstra和自定义对象和属性
我想在程序的其他部分使用boost 's dijkstra algorithm (since I' m . 我遇到的问题是将自定义对象（我相信它们被称为 property ）添加到 adjacency_list . 基本上我有一个自定义边缘类，它维护有关边缘和通过它连接的顶点的各种信息 . 我想使用 adjaceny_list 所需的边缘属性存储我的自定义数据对象 我已经成功实现了boost p...