回答情况：
提问时间：
问题标签：
它在解决最短路径问题上似乎非常有效。然而，我不知道如何用它来计算单源最短路径。更准确地说，在给定固定起点的情况下，计算在给定距离限制内可以到达的所有位置的最短距离(例如，30分钟内可到达)。OSRM是否提供API来计算单源最短路径问题(对距离有限制)？有没有其他免费的路由库更适合这种类型的问题？最好是具有对OpenStreetMap数据的良好支持的一个。
浏览 2修改于2015-12-03得票数 8
回答已采纳
1回答
我已经设法解决了使用dijkstra在恰好有一个负边时找到所有单源最短路径的问题。现在我正试图面对一个新的问题，当只使用dijkstra (而不是bellman ford)时，如何找到从给定来源到恰好K条负边的所有最短路径。(k是已知的)。
我真的想不出一个好的办法。
浏览 10修改于2013-07-04得票数 2
1回答
设s∈V是给定的源顶点。如何找到一种算法，找到所有顶点的距离，肯定比Bellman Ford的O(VE)时间复杂度更快。
浏览 4修改于2022-01-17得票数 0
回答已采纳
设s∈V是给定的源顶点。如果从s到任何其他顶点的最短路径至多需要k条边，并且我们不知道k是什么，那么如何设计一个算法来求解运行时间为O k(|V |+ |E|)的单源最短路径问题。
浏览 2提问于2019-03-12得票数 0
1回答
假设我们有一个n×n国际象棋棋盘(换句话说，就是一个矩阵)，每个方格都有一个权重。一块可以水平或垂直移动，但不能对角移动。每一次运动的费用等于棋盘上两个方格的差额。使用一种算法，我想要找到一个棋子从正方形(1,1)移动到平方(n，n)的最小代价，它在多项式时间中具有最坏的时间复杂度。伪码：
我们有一些空集S，一些整数V，并输入一个无权图。在此之后，我们完成了一个邻接矩阵，表示没有无限加权顶点的边的代价，而当矩阵没有选择所有的顶点时，我们找到一个顶点
浏览 2修改于2015-10-13得票数 0
回答已采纳
有许多最短路径实现(Dijkstra、Belman等)
我需要一个单一的来源最短的路径，一个未加权的图表。但问题是，从原始BFS到实际获得单个源最短路径仍有一个(非常小的)步骤，我应该编写自己的UnweightedSingleSourceShortestPaths类吗？
浏览 4修改于2015-05-26得票数 1
嘿，我一直在研究“单源最短路径”问题的贝尔曼-福特算法。但贝尔曼·福特算法在这里不起作用。
有人能建议我怎么做吗？
浏览 2提问于2012-05-13得票数 0
回答已采纳
假设s ∈ V是给定的源顶点。如果从s到任何其他顶点的最短路径至多需要k edges，如何设计一个算法来求解在时间O(k(|V | + |E|))内运行的单源最短路径问题
浏览 7修改于2019-03-12得票数 3
这是一个没有负边权重的单源最短路径问题。据我所知，对于此类问题，具有最佳大O运行时间的算法是Dijkstra，使用斐波那契堆作为优先级队列，尽管实际上二进制堆更容易实现，并且工作得也很好。
浏览 4修改于2015-01-22得票数 1
回答已采纳
根据问题的具体情况，在单源最短路径问题中通常提到的两种算法是Dijkstra算法和Bellman算法。Dijkstra的算法工作在正边权值，而Bellman算法是一个推广，也允许负边权。
浏览 7提问于2015-04-18得票数 0
在一个问题中，给出了一个只有正权值及其直径(即G中每对顶点中最大最短路径)= D的图G。该问题要求一个单源最短路径算法，该算法比Dijkstra快，在O(V+E+D)时间内运行。
浏览 2提问于2021-03-10得票数 2
对于无向图，Dijkstra的单源最短路径算法是最有效的算法吗？我使用这个算法来计算从站1(开始节点)到站N(目的地节点)的公交线路的最低票价。连接中间站的路径有一个指定的车费(边缘权重).Note，该公交线路网络可以有
这个问题的细节可以在这里找到-
浏览 2修改于2020-07-03得票数 3
我试图想出一个使用BFS为无向加权图找到单源最短路径算法的解决方案。 我想出了一个解决方案，将每个边权重转换为顶点之间的x条边，每条新边的权重为1，然后运行BFS。我会得到一个新的BFS树，因为它是一棵树，所以从根节点到每个其他顶点只有一条路径。 我遇到的问题是试图提出以下算法的分析。每条边都需要访问一次，然后根据它的权重被分成相应数量的边。
浏览 26修改于2020-03-19得票数 2
回答已采纳
我希望得到最短的路径，但也要确保不超出一定的成本。
我已经尝试实现Djikstra的，如果我超过了成本，就简单地回溯(因为没有更好的术语)，直到我遍历整个图。然而，我正在寻找一种比这更快的解决方案。
浏览 2修改于2017-10-09得票数 3
}
在for循环中，我们检查的是if(dist[node] + 1 < dist[it])，而不是+1，我们是否可以对从节点到it的边缘进行加权，并使用该代码在无向加权图中计算从顶点到其他每个顶点的最短路径
浏览 2修改于2022-04-10得票数 1
我知道BFS可以用来在无权无向图中找到从源到目的地的最短路径。但是我想知道BFS是否也可以用于无权图和有向图？
浏览 3修改于2022-08-04得票数 -3
回答已采纳
如果dag包含从顶点u到顶点v的路径，那么在拓扑排序中，u先于v。在拓扑排序的顺序中，我们只对顶点进行一次遍历。当我们处理每个顶点时，我们放松每一条离开顶点的边缘。
我们不能使用Dijkstra的算法，因为边被允许有负权。
浏览 5修改于2016-05-16得票数 3
回答已采纳
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号