找到一个有向非负赋权图的最短路径，避免给定子集顶点的任何顶点相邻？
在云计算领域中，寻找一个有向非负赋权图的最短路径，并避免给定子集顶点的任何顶点相邻，可以使用以下方法：
- Dijkstra算法：Dijkstra算法是一种经典的最短路径算法，适用于有向非负赋权图。它通过维护一个距离数组来记录从起始顶点到其他顶点的最短距离，并逐步更新距离数组，直到找到最短路径。在给定子集顶点的情况下，可以通过修改算法来避免子集顶点相邻。
- A算法：A算法是一种启发式搜索算法，可以用于解决最短路径问题。它通过估计从当前顶点到目标顶点的距离，并综合考虑已经走过的路径长度和估计的距离，选择下一个顶点。在给定子集顶点的情况下，可以通过修改启发函数来避免子集顶点相邻。
- Bellman-Ford算法：Bellman-Ford算法是一种解决最短路径问题的动态规划算法，适用于有向图。它通过迭代更新每个顶点的最短距离，直到收敛为止。在给定子集顶点的情况下，可以通过修改算法来避免子集顶点相邻。
这些算法都可以通过编程语言来实现，如Java、Python、C++等。在实际应用中，可以使用腾讯云的相关产品来支持云计算任务，例如：
- 腾讯云弹性容器实例（Elastic Container Instance）：用于快速部署和管理容器化应用，提供高性能和高可靠性的计算环境。
- 腾讯云函数计算（Serverless Cloud Function）：无需管理服务器，按需运行代码，实现弹性扩展和高可用性，适用于处理短时任务和事件驱动型应用。
- 腾讯云云服务器（Cloud Virtual Machine）：提供灵活的计算资源，可根据需求选择不同的实例类型和规模，适用于各种应用场景。
以上是一些腾讯云的产品，可以根据具体需求选择合适的产品来支持最短路径问题的解决。更多产品信息和介绍可以参考腾讯云官方网站：https://cloud.tencent.com/
相关·内容
我最近一直在研究所有对最短路径算法，比如弗洛伊德-瓦赫尔和约翰逊的算法，我注意到这些算法产生了正确的解，即使一个图包含负权边(但不包含负权环)。作为比较，Dijkstra的算法(它是单源最短路径)不适用于负重边。是什么使全对最短路径算法在负权重的情况下工作？
浏览 9提问于2014-04-06得票数 6
回答已采纳
2回答
运行Johnson算法后的回溯
、、、、
我有一个问题，我以前在学校的一些考试中被问过，但我找不到答案。
在图上运行之后，是否有可能知道它以前是否有负循环？为什么？
Johnson算法
Johnson算法是一种能够计算图上最短路径的方法。这是能够处理负重的边缘，只要不存在一个循环负重。
该算法由(来自)组成：
首先，将一个新的节点q添加到图中，将零权边连接到其他节点。
其次，使用Bellman算法，从新的顶点q开始，为每个顶点v找到从q到v的路径的最小权重h(v)。如果此步骤检测到负循环，则终止该算法。
接下来，用Bellman算法计算的值对原图的边进行重加权:从u到v的一条边，具有长度w(u, v)，给出了新的
浏览 0提问于2018-09-04得票数 1
给定一些无向边权重图，什么算法可以用来寻找从某个顶点v到另一个顶点w的最短路径？
对于有向边权重图，您可以使用Dijkstra的最短路径算法，但我使用的是无向图，因此它不起作用。
对于不是边加权的图，您可以使用广度优先搜索(BFS)，但我使用的是边加权图，因此它不起作用。
因此，假设它既是无向的，又是边加权的，那么一般的最短路径方法是什么？
浏览 5提问于2019-10-07得票数 0
我不是要求一个算法来检查图中负圈的存在(Bellman Ford或Floyd Warshall可以这样做)，而是在图包含至少一个从源顶点可以到达的负圈，并且从负圈可以到达目标顶点的情况下，是否存在多项式时间算法来寻找两点之间的最短路径。
浏览 3提问于2013-09-02得票数 2
回答已采纳
2回答
设G(V，E)是一个无负圈的有向连通图。除一条边外，所有边都有非负权.在V中找出一条从s，t到t的简单最短路径。
我的主意-
在图上做一个BFS，找出负重的边。
把这个负重加到所有的边上，这样我们就消除了负重。
做Dijkstra算法。
我的主意行不通。
你能帮我找出原因吗？
谢谢。
浏览 0提问于2018-06-15得票数 0
回答已采纳
2回答
我正在看一个关于负面循环的讲座。
在5:00，教员描述了假设不存在周期的情况。然后他说，任何一条路径都不会包含一个循环，因为如果一条路径存在于一个循环中，人们就可以显示一条没有循环的较短的路径，而这个周期可能只有非负的。
有人能帮我理解这一点吗？我好像听不懂。
谢谢。
浏览 10提问于2014-01-01得票数 1
回答已采纳
2回答
最小生成树和最短路径
、、、
我遇到了这样一个问题：
给定一个具有整数权重(正负)的连通有向图，开发一个算法来寻找两个顶点之间的最短路径。
我想我可以使用最小生成树算法，例如kruskal的算法，然后使用可能的dijkstra算法来证明，因为在MST中，每个顶点只有一条进入边，dijkstra的算法甚至可以在负权重下工作。
这听起来很夸张吗？
附注：我很难证明MST包含每个顶点的有向图的最短路径。
浏览 1提问于2012-11-08得票数 0
1回答
我想弄明白为什么有人更喜欢弗洛伊德-沃夏尔而不是迪克斯特拉：
Dijkstra使用一个可以理解的系统，结合回溯，给出了一个正确的结果。
弗洛伊德-沃夏尔做了一个完整的名单和过滤器在那里。
我唯一能想象的是巨大的图表，在这种情况下，Dijkstra只给出了一个解，结果是给出结果的时间非常长。弗洛伊德-华沙尔，然而，已经开始吐出不同的可能性，并试图一点一滴地改进(例如，基于启发式)。但如果这是真的，那么迪克斯特拉就不会也是这样吗？
还是有其他原因我没有想到这里？
请注意:我正在处理的图是“典型”图，其中车辆需要从一个地方到另一个地方，边的权重等于顶点之间的距离(这是我所走过的点)。边可能是定向的，
浏览 0提问于2023-01-20得票数 1
回答已采纳
2回答
给出了一个有向图，其中每个边都有一个cost.Taking优点，即图中最多有两个负边，我的目标是求出从给定节点到V中所有节点的最短路径距离。算法的时间复杂度应该是O(|E| + |V|*log|V|)，所以我认为需要应用Dijkstra算法。
我猜想我需要以某种方式将我给定的图转换成一个新的图，该图中从s到v的最短路径将等价于给定图中所需的最短路径。或者我需要修改Dijkstra的算法？
我现在很挣扎。任何帮助都将不胜感激！
浏览 4提问于2014-02-04得票数 0
回答已采纳
如果唯一的负边成本来自初始节点，该怎么办？这个算法还能工作吗？
我觉得是，因为我想不出反例，但我很难证明这一点。有反例吗？
负边对于Dijkstra来说是一个问题，因为如果有一条边可以稍后选择，并且很大程度上是负权重的，那么就不能保证你选择的边会产生最短的路径。但是，如果只有负边来自初始节点，我就看不出问题了。
我不是在找一个算法。我在找一些关于Dijkstra的东西。
我说的是有向图，如果有区别的话。
浏览 0提问于2010-10-01得票数 16
回答已采纳
1回答
有向无圈图的最小方差路径
、、、、
给定一个DAG，其中每个节点都有一个数值。我希望通过具有节点值最小方差的图获得路径。
回顾一下，在有向无环路径中，哪一种算法是寻找最小方差路径的最佳算法？
谢谢你，皮耶罗
浏览 4提问于2015-04-10得票数 0
回答已采纳
我有一个有向图，它有圈。所有的边都是加权的，并且权重可以是负的。可能会有负循环。
我想找到一条从s到t的路径，它最小化了路径上的总重量。当然，当负循环存在时，它可以进入负无穷大。但是，如果我不允许在路径中循环(而不是在原始图中)，该怎么办？也就是说，一旦路径离开一个节点，它就不能再次进入该节点。
这无疑避免了负无穷大问题，但令人惊讶的是，谷歌搜索没有发现任何已知的算法。最近的是弗洛伊德-沃尔算法，但它不允许负循环.
提前谢谢。
编辑:我可能把原来的问题概括得太多了。实际上，给出了一个具有非负边权的循环有向图。此外，每个节点也有一个积极的回报。我想找到一个简单的路径，它最小化(路径上的边权和)-
浏览 2提问于2013-10-22得票数 2
回答已采纳
2回答
研究贪婪算法。总结一下Dijkstra算法的一些重要方面，这是正确的。我怀疑(4)和(1)，有人能帮我吗？
(1)如果所有边权都为负值，Dijkstra算法工作良好。
(2)如果图中有负圈，则Dijkstra进入无限循环，且永不结束。
(3)如果一个图有一个负权边，但没有负循环，则该算法不能很好地工作。
(4)如果图没有负循环，则算法工作良好。
浏览 6提问于2015-02-18得票数 2
回答已采纳
我们知道Bellman Ford是一个寻找负循环的算法。这里是Bellman Ford输入的算法:给定一个图G(V，E)，w(e)是权重输出:如果存在负循环，则返回Yes。
1: set d(s) = 0 and d(v) = 1 for all v (- s
2: for i = 1 ... n-1 do
3: for every edge (u, v) in G do
4: if d(v) > d(u) + w(u,v) then
5: d(v) = d(u) + w(u,v)
6: end for
7: end for
8: f
浏览 0提问于2014-06-26得票数 1
3回答
我很难理解MST是否会是一棵树。
假设图G= (V，E)，做连接V中所有顶点且总权重最小的边T⊆E的子集必须是一棵树，或者当-一些边可能有负权时，它是否是其他子图。-所有的边缘都有正的权重。
我在想，对于一些可能有负权的边，它必须是一棵树，对于所有边都有正权的边，它可以是其他一些子图。
如果我是对的还是错的，请帮助我。
如果它一定是一棵树，你能用连接性和最小性来解释矛盾吗？但是如果你认为它可能是其他的子图，那么你能给我举一个例子吗，一个可能不是树的连通图的权重较低。
浏览 3提问于2013-11-11得票数 0
3回答
最小生成树害怕负权重吗？
、、、
这是的后续问题。
我认为最短路径(SP)有负权重的问题，因为它将路径上的所有权重相加，并试图找到最小的一个。
但我不认为最小生成树(MST)有负权重的问题，因为它只取单个最小权边，而不关心整体的总权重。
我说的对吗？
浏览 7提问于2012-05-02得票数 56
回答已采纳
1回答
我需要在下面的图中计算从A到B的两条路径，约束条件是这些路径不能共享任何边：
嗯，好吧，不能上传图片，这是个。
所有的边都有正权重；对于这个例子，我认为我们可以假设它们是相等的。我的简单方法是使用Djikstra的算法来计算第一条路径，如上图中的第二张图所示。
然后，我从图中删除边，并尝试计算第二条路径，但失败了。有没有Djikstra，Bellman-Ford (或其他任何东西)的变体，可以计算上面第三张图中显示的路径？(我的意思是，不需要特殊知识，也不需要删除转载链接)
浏览 0提问于2010-05-11得票数 0
我的问题是：
我有一个无向图。每条边都有一个成本(或重量)。其中一个节点被标记为S。我想从S开始，至少访问每个节点一次。允许多次访问节点。允许多次沿边缘旅行，尽管这将使解决方案更加昂贵--以3倍的成本沿边旅行将使整个路径的成本增加6倍。这个图有一些“死胡同”的节点，所以有时我们不得不不止一次地遍历一个边。
什么是快速算法来做到这一点？这是一个众所周知的问题吗？
我要找的是：
相当快--我们这里讨论的图的相对大小是40-50个节点的顺序。所以这个算法希望不会超过10-15秒。
合理的最优--我不是在寻找绝对的最优性。任何有趣的启发式引导搜索，以使解将接近最优是足够好的。
我将用python写这篇
浏览 3提问于2012-09-05得票数 4
1回答
我如何在Bellman算法中证明这一点：
如果没有负权循环，那么从源s到接收器t的每条最短路径最多都有n-1边，其中n是图中的顶点数。
有什么想法吗？
浏览 0提问于2018-05-24得票数 3
回答已采纳
1回答
把图划分成组的算法
、、、、
我正在寻找一种算法，将一个图划分成最大大小为n的顶点组(如果每个顶点都是自己的图，则每个顶点是连通的)，同时保持最小的组数。我需要这个算法将delaunay三角剖分划分成每个区域的顶点数相等的区域。如果有人有更好的想法来解决这个问题，请告诉我！
浏览 2提问于2013-11-27得票数 3
回答已采纳
图G是一个无向图，它的所有边的权重都是相同的。u，v是2个给定的顶点，如何在O(|V|)中求出图G中u和v之间的最短路径的个数？
|V|表示G中的顶点数。
浏览 0提问于2014-12-21得票数 1
2回答
我正在做一项任务，它让我遍历一个简单的正方形图，目的是积累最少的危险。终点很简单:从左上角到右下角。我只限于水平和垂直移动之间的顶点。地牢里的每个房间(图上的每个顶点)都有一个特定的危险等级。
示例：
0 7 2 5 4 0 -> 1 -> 1 -> 2 -> 2 -> 1 -> 3 -> 1 -> 0
1 5 1 2 1
1 2 2 1 1
1 9 5 3 5
1 1 9 1 0
我一直在抛出使用优先级队列的想法，但我仍然不知道如何，确切地说，我会在第一时间使用那个P。
我可以尝试Dijkstra的算法，但我不是计算节点之间的距离，而是
浏览 0提问于2015-05-12得票数 1
回答已采纳
2回答
今天我遇到了这个词“单对最短路径问题”。我想知道对加权图是否存在单对最短路径算法。我的推理可能有缺陷，但我想，如果你想找到A和Z之间的最短路径，你绝对必须知道从A到B，C，D，……的最短路径。Y.
如果你不知道后者，你就无法确定你的道路实际上是最短的。因此，对于我来说，任何最短路径算法都必须计算出图中从A到其他顶点的最短路径，才能得到从A到Z的最短路径。
这是正确的吗？
如果是的话，有研究报告证明这一点吗？
浏览 4提问于2017-03-30得票数 10
回答已采纳
1回答
图中的最短路径
、、
给定一个具有N (1 <N≤1000)个顶点和正权的无向图G。找出从顶点1到顶点N的最短路径，或者声明该路径不存在。
提示:在每个步骤中，在尚未检查的顶点中，找到从顶点1到它的最短路径的顶点，选择从顶点1到它的路径最短的顶点。
我在topcoder上发现了这个问题，我认为应该使用Dijkstra的算法，但这篇文章是关于动态编程的，而Dijkstra是一个贪婪的算法。
谁能告诉我解决这个问题的最好方法。
谢谢
浏览 3提问于2016-07-28得票数 1
1回答
我目前的理解是，dijkstra的算法比贝尔曼-福特算法更有效，只是它不能处理负边缘。然而，假设我们有一个边权重图，其中有负权重的边，图中没有负权重的圈，我们还能使用dijkstra算法吗？
浏览 7提问于2019-11-28得票数 2
1回答
问题是如何从起始顶点到directed graph中的所有其他顶点寻找最短路径。
但是图有m positive加权边和k negative加权边，并且保证了负加权边不会在一个循环中。换句话说，在这个图中没有负的加权循环。
我试图直接使用Bellman-Ford和SPFA来解决这个问题，但是有没有更快的方法来解决这个问题呢？
浏览 4提问于2020-12-16得票数 3
回答已采纳
1回答
确定哪组边会导致负循环？
、、、、
我有一个有向图G= (V，E)，其中边有权。某些边可能具有负权重，但G不包含任何负循环。
我有一组新的边S，如果加到G上，会导致一个负循环。我想确定这些边中的哪一个，当加到G上时，会导致负循环。我怎么能这样做呢？
浏览 1提问于2014-05-02得票数 2
这个提到：
加权图G中两个给定顶点之间的最长路径与图−G中的最短路是一样的，它是由G导出的图的最短路。因此，如果在−G中可以找到最短路径，那么在G中也可以找到最长的路径。
那么，如果这种变换可以将最长路径简化为最短路径问题，那么为什么寻找最长路径是NP难问题呢？
在转型之后，我们有这样的情况：
-G有一个负循环，在这种情况下，无法找到-G中的最短路径。
-G不存在负循环，在这种情况下，Floy或Bellman算法可以在多项式时间内找到-G中的最短路径。
问题：
如果没有负循环，那么寻找最长路径的问题就不是NP难问题了，这样说对吗？
在负循环存在的情况下，节点之间
浏览 2提问于2018-11-20得票数 7
回答已采纳
1回答
作为一个练习，我必须建立一个卫星导航系统，计划最短和最快的路线从地点到地点。它必须尽可能快，我可以做到这一点，而不用太多的内存。
我很难决定用哪种结构来表示图形。我知道矩阵对稠密图更好，列表更适合稀疏图。我更倾向于使用列表，因为我假设添加顶点将是这个程序中最麻烦的部分。
我只想听听你们的意见。如果我把一个典型的路线图看作是一个图，其中不同的位置是节点，道路是边缘。你认为它是稀疏的还是密集的？在这种情况下，哪种结构看起来更好？
浏览 1提问于2016-04-19得票数 3
回答已采纳
1回答
给定有向无权图G，V中的一组蓝色顶点B和(V)中的黄色顶点y，我需要在访问一个蓝色顶点之后，在不访问黄色顶点的情况下，找到从给定源到图中所有其他顶点的最短路径。换句话说，如果已经访问了一个蓝色顶点，则不允许访问黄色顶点(可能有些顶点是不可访问的)。
以下是我的想法：
运行BFS有点不同--如果我们在B中的一个顶点b处传递，不要继续搜索b的邻居。当BFS完成时，如果所有的顶点都被标记了，我们就完成了。否则：
在B中的每一个b上运行BFS(b)，对于从b到y的每条路径，删除路径中的最后一个边。例如，BFS(b)找到路径b，s，y，然后删除(s，y)。
运行BFS。
复杂性将是O
浏览 2提问于2013-11-18得票数 3
回答已采纳
2回答
在编写bellman算法的程序时，我遇到了一个问题，这个问题更多的是理论问题，而不是技术问题，但这里是：
我有4点A，B，C，D，从A到B等于3的成本，这是图：
B--3--C
| |
3 9
| |
A--1--D
假设我想知道通过D从A到C的成本是多少，它会是：10吗？或者从A到D(成本是1)，然后从D回到A(总成本是1+1=2)，然后从A到B (1+1+3=5)，从B到C (1+1+3+3=8)，所以它是8而不是10？
我到处找，但我没有找到任何理性的答案我的问题。
编辑：
假设A->D和D->C路径数为2，对于A-> D ->A ->
浏览 2提问于2012-09-17得票数 0
回答已采纳
我在这个问题上已经困了两天了，至今仍未取得任何进展。基本上问题是这样的:给定一个无向简单加权连通图，在访问给定集合的至少一个顶点时，我们必须找到从给定源到给定目的地的最短步行，同时访问集合B中的至少一个顶点，附加的约束条件是，集合B的顶点应该总是在访问集合A的顶点之后才能到达，而且图中可能存在既不属于A也不属于B的顶点。
我试着把最短的路径分解成一个访问顶点的路径，从A到B，从v到另一个，然后从w到目的地。这可以分别使用不同起始点的Dijkstra 3道次进行。但是，我必须选择这样的最小v，从而导致O(V_E_log(V))复杂度，其中V=顶点数，E=边数。我对如何在O(E*log(V))中这
浏览 2提问于2020-06-07得票数 1
回答已采纳
3回答
Dijkstra算法能否找到从一个源顶点到所有其他顶点的所有最短路径，使得该路径访问一个无向对称图中的所有顶点一次且恰好一次？对称图有没有更快的算法？
浏览 1提问于2013-06-07得票数 4
回答已采纳
该算法如下：
该算法首先对数据进行拓扑排序(参见第22.4节)，在顶点上强制线性排序。如果dag包含从顶点u到顶点v的路径，那么在拓扑排序中，u先于v。在拓扑排序的顺序中，我们只对顶点进行一次遍历。当我们处理每个顶点时，我们放松每一条离开顶点的边缘。
谁能告诉我背后的直觉吗？使用这种直觉，请告诉我们如何找到最长的路径，只要取取边权值，并运行算法。
我们不能使用Dijkstra的算法，因为边被允许有负权。
浏览 5提问于2016-05-16得票数 3
回答已采纳
1回答
我有一个问题，如下所示，我真的坚持它，因为它运行超过我想要的时间(大约1秒)。我真的希望你能帮我建立一个比我的算法更有效的算法
给出了一个无向图G= (V，E)，每个边的权值分别为w1和w2。该图有N个顶点和M个边。一个K-初等路径S是G的一个子图，它必须是一个初等图，而且它确实有K个边。
找出一条K-初等路径S，以所有边的w1和作为最小值，S的所有边的w2之和必须小于给定值Q，如果它不存在任何满足的路径，则打印出值-1。
输入：
具有四值N，M，K，Q (2 <= N，K <= 50，1 <= M <= 2*N，1 <= Q <= 10^9)的第一条线
浏览 2提问于2021-01-13得票数 2
1回答
加权无圈图上的码
、、、、
我们有一个关于带正边和负边的加权无圈图G(V, E)的码。我们用下面的代码来改变这个图的权重，给出一个没有负边(G')的(G')。如果V={1,2...,n}和G_ij是边i到边j的权重。
Change_weight(G)
for t=1 to n
for j=1 to n
G_i=min G_ij for All K
if G_i < 0 (we have a bar on G)
G_ij = G_ij+G_i for all j
G_ki = G_ki+G_i for all k
我们有两
浏览 0提问于2015-02-19得票数 3
回答已采纳
3回答
我一直在为编程竞赛做准备，我偶然发现了这个问题，在这个问题中，我必须用加权和无向图从源到目的地找到最短的路径，但是我必须跳过每一条边(所以它的权重并不重要)。图中的权重是正整数。
原始声明：
克拉拉和杰克正在旅行。他们轮流开车，每个城市之后，汽车司机都被换上了。找到从源头到目的地的最短路径，克拉拉开的路程最少。先写谁应该是汽车司机。
解决这个问题的最佳方法是什么？是否有任何算法的任何修改，以解决它容易？
编辑:跳边的权重等于0，如果边可以跳过或者不能跳过，我必须检查这两个选项。
浏览 0提问于2018-06-06得票数 6
回答已采纳
1回答
交通灯图
、、
假设您有一个标准图，并将值附加到每个节点和每个边缘。您希望在最短的时间内从图上的一个节点转到另一个节点。到目前为止，遍历此图所花费的时间将称为T。如果边的值为V，遍历该边将使您花费的时间增加V (T += V)。如果节点有一个值N，遍历该节点将迫使您等待，直到您花费的时间可被N (T += (N % N) % N)整除。
你可以把它想象成街道和交通灯。在街上开车需要一定的时间才能到达另一端。开车穿过红绿灯需要等很长时间才会变绿。
例如，假设您有这样的图：
S--6--[1]--2--[7]
| |
3 2
| |
浏览 2提问于2014-10-13得票数 1
回答已采纳
2回答
根据算法书Corman的说法，Dijkstra只适用于所有边都具有非负权的图。这是否意味着，如果有任何负权重的边，它将不工作的整个图？还是不算负重边？请指出哪个是对的？
浏览 0提问于2013-08-09得票数 4
4回答
给定一个有向图G=(V,E)，两个顶点s，t和两个权重函数w1，w2，我需要在<代码>D10</代码>从s到t的所有最短路径中找到w2到s的最短路径。首先，如何找到两个顶点s和t之间的所有最短路径？Dijkstra的算法帮助我们找到从一个顶点到每个其他可访问顶点的最短路径，是否可以修改它以获得两个顶点之间的所有最短路径？
浏览 0提问于2013-05-11得票数 4
我的图不包含将顶点连接到自身的边。两个顶点之间只有一条边。从上我了解到了一些根据给定条件计算最短路径的算法。最著名的算法之一是Dijkstra's algorithm算法，它寻找从源顶点到图中所有其他顶点的最短路径。
但是通过使用Dijkstra's algorithm，我不需要探索所有的顶点，然而我的目标只是找到从单个源到单个目的地的最短路径。我应该在这里使用哪种策略？这样我就不需要探索所有其他的顶点了。
我的一种方法是使用bidirectional bfs。我所说的bidirectional bfs是指应用两个bfs，一个来自source node，另一个来自destina
浏览 0提问于2012-04-07得票数 2
回答已采纳
我有一个任务，要求我计算出一个完整的无向图的最短路径。该问题给出了一个完整的无向图，基本算法(BFS和DFS)可以提供最短路径。考虑到BFS是一个完全无向图，我想知道使用BFS还是DFS是否会产生相同的输出。
浏览 5提问于2021-05-12得票数 0
回答已采纳
4回答
public int dijkstra(){
boolean[] visited = new boolean[gSize];
int src = 1;
int dest = 1;
int[] distance = new int[5];
int[] part = new int[5];
int min;
int nextNode = 0;
for(int i = 0; i < 5; i++)
{
visited[i] = false;
part[i] = 0;
浏览 8提问于2015-09-22得票数 2
回答已采纳
我很难找到一个很好的办法来解决汇率问题。我花了一整天的时间来思考这个问题，并为所有情况提供了一个优雅而快速的解决方案。
声明：
我们有一些汇率，比如.
欧元兑美元-> 1.37
美元兑澳元-> 0.7
从MEX到CAD -> 1.8
日元兑日元-> 2.3
(.)
这一比率不是真实的，可能每天变化一次。利率的数量可能和世界上的货币一样大(约150种)。
我们被要求将一笔钱从任何一种货币兑换成另一种货币，如果可以的话，我们应该给出汇率的答案。
最好的情况是，如果您的汇率是直接的(出现在列表中)，那么在更糟糕的情况下，您应该在中间汇率中跳过很多次
浏览 2提问于2013-12-15得票数 6
1回答
我有一个具有非负加权边的有向图，其中两个顶点之间有多个边。
我需要计算所有对最短路径。这张图很大(20毫升的顶点和100毫秒的边)。弗洛伊德-沃尔是最好的算法吗？有一个好的库或工具来完成这个任务吗？
浏览 0提问于2019-03-18得票数 0
回答已采纳
我正在开发一个程序，在二维空间中，一个随机的点集使用Delaunay三角剖分生成一个图。
对于这一部分，有大量的算法可以做到这一点。
我要实现的第二部分是对点进行放松，即允许它们在2D空间中移动，以便彼此之间的距离相等。
我知道，对于Voronoi图( Delaunay三角剖分的对偶图)，劳埃德算法可以执行这个任务，但是我似乎找不到任何独立于这个图结构的算法(除了这个松弛步骤之外，我不需要计算这个算法)。
关于我需要的算法类型有什么提示吗？
提前感谢！
浏览 3提问于2015-10-26得票数 0
回答已采纳
2回答
最宽路径的Floyd算法
、、、、
我一直在研究加权有向图的图算法，特别是Floyd关于所有对最短路径问题的算法。这是我的伪代码实现。
设G是一个具有节点{1，…，n}和邻接矩阵A的加权有向图。设B_k i，j是从i到j的最短路径，它使用中间节点<= k。
input A
if i = j then set B[i, j] = 0
set B[i, j] = 0
else if i != j && there is an arc(i, j)
set B[i, j] = A[i, j]
else
set B[i, j] = infinity
#B = B0
for k = 1 to n:
浏览 8提问于2021-02-22得票数 1
当图G分别具有顶点和边，顶点u和t时，编写一个O(|E|+|V|)算法计算从u到t的最短路径数，即如果有5条长度4的路径，长度4是从u到t的最短路径，则算法输出5条。
我知道算法必须以某种方式合并DFS或BFS，因为每个算法都有一个O(|E|+|V|)运行时，但我有点卡住了。我尝试实现这样的东西:它会反复执行DFS，算法终止于t，但在决定将哪些节点设置为已访问的节点以及在每次迭代后重置哪些节点时，这就成了问题。
提前感谢！
浏览 0提问于2019-04-17得票数 0
回答已采纳
给定一个无向赋权图G(V，E)。求G的一个顶点x，使得dist(u，x) + dist(v，x) + dist( w，x)是最小的。X可以是G中的任何顶点(包括u、v和w)。对于这个问题有什么特别的算法吗？
浏览 2提问于2016-08-01得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
