有时间约束的最短路径
最短路径是指在一个加权有向图或无向图中，找到两个顶点之间的最短路径，即路径上的边权重之和最小的路径。常用的最短路径算法有Dijkstra算法和Floyd-Warshall算法。
Dijkstra算法是一种贪心算法，用于解决单源最短路径问题。它通过维护一个距离数组，不断更新起始点到其他顶点的最短距离，并选择当前距离最小的顶点作为下一个中间顶点，直到找到起始点到目标点的最短路径。
Floyd-Warshall算法是一种动态规划算法，用于解决全源最短路径问题。它通过维护一个距离矩阵，不断更新任意两个顶点之间的最短距离，通过遍历所有顶点作为中间顶点，逐步缩小距离矩阵的值，最终得到所有顶点之间的最短路径。
最短路径算法在实际应用中有广泛的应用场景，例如路由算法、导航系统、物流规划等。在云计算领域中，最短路径算法可以用于优化数据中心内部的网络通信，提高数据传输效率和响应速度。
腾讯云提供了一系列与最短路径相关的产品和服务，例如：
- 云服务器（CVM）：提供高性能、可扩展的虚拟服务器，可用于构建网络通信和计算资源。
- 云数据库MySQL版（CDB）：提供高可用、可扩展的关系型数据库服务，可用于存储和管理最短路径算法中的图数据。
- 云网络（VPC）：提供灵活的网络配置和管理，可用于构建数据中心内部的网络通信。
- 云监控（Cloud Monitor）：提供实时的监控和告警服务，可用于监控最短路径算法的性能和运行状态。
- 云函数（SCF）：提供事件驱动的无服务器计算服务，可用于实现最短路径算法的自动化调度和执行。
以上是腾讯云相关产品和服务的简要介绍，更详细的信息和产品介绍可以参考腾讯云官方网站：https://cloud.tencent.com/
相关·内容
1回答
你的朋友X最近买了一辆雷鸟摩托车。他非常兴奋，想把车从一些城镇开到塔尔沙漠的另一个城镇(如果你更喜欢冒险，就想想撒哈拉沙漠吧)。他被提供了完整的沙漠路线图-道路，它们的长度和交叉点(两条或更多条道路相交的地方)。摩托有一个非常自然的限制-它可以在充满油箱的情况下行驶c公里。由于目的地很远，X必须计划他的路线，这样他就可以在路上重新加满油箱。请注意，最短路由不一定是可行路由。你的朋友有点困惑和害怕--如果他因为计划不当而在塔尔沙漠迷路了怎么办？你的朋友为你感到骄傲。他还知道你上过一门关于算法的课程。他满怀信心地接近你，相信你会帮助他找到从s到d的最短可行路径。用一个加权的无向图对问题进行建模，
浏览 10提问于2020-11-01得票数 1
回答已采纳
1回答
在一个标准的线性赋值问题中，我可以用匈牙利算法实现O(n^3)。如果添加了额外的约束怎么办？示例：
具有4代理的“正则”LAP有约束矩阵
结果向量b=111。
匈牙利算法将像预期的那样解决这些问题。但是，如果添加了另一个约束，例如约束矩阵是
结果向量b=11 1 1 1 0？
也就是说，除了在标准线性和约束下最小化成本函数之外，我还必须考虑如下约束
此和产生上述附加矩阵中的最后一行。
显然，由此产生的约束矩阵不再是完全单模的。当然，标准的MILP会解决这个问题，但是它是NP难的。我的问题是:是否有一种类似匈牙利的算法，可以在多项式时间内解决这个问题？
浏览 9提问于2017-10-23得票数 1
回答已采纳
1回答
def shortestPath(digraph, start, end, maxTotalDist, maxDistOutdoors, visited=[]):
if not (digraph.hasNode(start) and digraph.hasNode(end)):
raise ValueError('Start or end not in graph.')
path = [str(start)]
if start == end:
return path
shortest = None
Mini
浏览 0提问于2011-05-07得票数 0
我使用的是python 2.7和networkx。
我有一个相当大的网络，我需要找到起点和目的地之间的所有路径(不仅仅是最短路径)。由于我的网络很大，我想在一些限制条件下加快速度，例如路径长度、成本等。
我正在使用networkx。我不想使用all_simple_paths，因为使用all_simple_paths之后，我必须根据路径长度(其中的节点数)或路径的成本(基于弧成本)来过滤所有路径。过滤所有路径对于大型网络来说是非常昂贵的。
我真的很感谢任何人的帮助。
浏览 16提问于2016-09-15得票数 0
1回答
我试图从Skiena的算法设计手册中解决以下问题
8-16考虑一个城市，其街道由X，x，Y网格定义。我们感兴趣的是从网格的左上角走到右下角。不幸的是，这座城市有着糟糕的社区，我们不想走进这些街区的十字路口。给出了一个坏的X×Y矩阵，其中BADi，j=“是”当且仅当街道i和j之间的交点在一个邻域以避免。(c)给出一个O(XY)算法，以在网格中找到避免不良邻域的最短路径。您可以假设所有块都具有相同的长度。对于部分信用，给出了O(X^2*Y^2)算法。
这个问题来自于关于动态规划的章节，在“图问题”的标题下。我知道我可以把它建模成一个无向无权图，它包含所有“好”交点和相邻“好”顶点之间的边的顶
浏览 1提问于2017-01-04得票数 0
1回答
使用限制提升c++ Astar
、、、、
我使用的是boost 的astar算法
我想为从起始节点到目标节点的路径长度积分一个长度条件。更具体地说，我试图找到一个精确长度为11位的数字链。一个想法可能是集成到boost A*实现的访问者模式中。但到目前为止，我还没有找到好的解决方案。
更一般的是，我正在寻找一种方法，将语法检查集成到A*算法中。在我的具体例子中，语法可以用一个规则模式来表示，比如^1-9\d{10}$每个节点代表一个字符(这里是一个数字)。任何建议都是值得感谢的。
浏览 2提问于2017-12-27得票数 0
1回答
统计DAG中通过节点的最短路径数
、、、、
我正在寻找一种算法来计算DAG中穿过特定节点的路径数(类似于“介于”的概念)，具有以下条件和约束：
我需要对图中的一组源节点/目的节点进行计数，而不是对所有节点进行计数，即对于中间节点n，我想知道从节点集合S到节点集合D有多少条不同的最短路径通过n(这里的不同是指至少有一个非公共节点的每两条路径)
考虑到DAG可能非常大，但边很稀疏，因此不会优先考虑节点上的深度嵌套循环，因此您可能会建议使用哪些算法来实现此目的。
浏览 0提问于2011-09-24得票数 6
回答已采纳
1回答
我被困在这一点上最大化d_t在第4页。我绝对听不懂作者的论点
这些松弛约束意味着，在任何可行的解中，d_v是从s到v .Thus的最短路径距离，与之相反的是，我们正确地最大化了目标函数来计算最短路径！
我们正在寻找最短的路径，但为什么我们要寻找最大的d_t？
浏览 2提问于2017-03-26得票数 1
回答已采纳
1回答
我正在研究一个只有一个仓库的车辆路径问题。问题定义如下。有n辆汽车需要到m个站点。每个站点都有其特定的限制，比如只有具有一定容量的车辆才能为站点提供服务，一些站点需要在一天中的特定时间提供服务。此外，车辆将具有不同的能力，并将有不同的开始和结束时间。
这个想法是为了最大限度地减少车辆从仓库出来的旅行时间。
我正在为这个问题构建成本矩阵。虽然不是图论方面的专家，但我知道，如果问题落入经典的旅行商问题，我可以使用哈密顿循环来解决它。然而，因为它落入了一个多旅行商问题，我想知道我如何使用哈密顿循环来解决这个问题，或者是否有另一个专门设计的过程来解决这样的问题？
任何帮助都将不胜感激。
浏览 0提问于2010-12-08得票数 5
回答已采纳
1回答
我是新的传单，我需要创建一个层之间的最短路径节点。我还需要一些其他计算的折线。我尝试了一些插件，这些插件只显示地图上最短的路径，但没有提供更多的细节(polyline，点对点.)最优路线。有什么办法能让我得到数据吗？任何插件或把戏.？
浏览 3提问于2016-03-21得票数 1
回答已采纳
3回答
具有指定目标的星型搜索算法非常简单。但是，如果一个图中有多个目标呢？例如，您可能希望找到必须包括以前指定的节点的最短路径。这里的约束条件是，您的路径必须包括A、B和C节点(或更多)，而不仅仅是查找到节点A、B或C的路径。当然，图中包含一个或多个A、B、C类型节点。因此，有一个问题:我如何适应--多目标的A星搜索算法
编辑:我们可以访问多个节点。
浏览 3提问于2012-03-04得票数 5
回答已采纳
如果给定图中的所有边都有相同的权重，Dijkstra的算法还能找到两个顶点之间的最短路径吗？谢谢!
浏览 6提问于2014-01-24得票数 3
回答已采纳
如何在不遍历所有图的情况下找到导致某些其他节点的所有节点？(有向图)
有办法做这个吗？
是否有一些技术或算法可以帮助执行此任务而不必遍历所有图表？
更新
假设你的图有3条可以到达A的路径，你如何在不遍历所有图的情况下找到这3条路径？我不想要其中的一条路，而是所有的树。我来自关系数据库，在我看来，索引是索引，但是图表是不同的，所以我想问的是，是否有一种方法可以在不遍历所有图的情况下找到通向A的所有节点。或者在最坏的情况下，只遍历一次，然后我就可以查询结构中的路径。
从SQL的角度来看，这类似于：
SELECT nodes.id
FROM Graph
WHERE node.destinat
浏览 14提问于2020-05-15得票数 1
3回答
如果我已经在迷宫中完成了A*算法的实现，以便找到通向单个目标的最短路径(就像pacman游戏一样)，那么我应该如何改进当前的启发式算法(曼哈顿到目标的距离+从一开始到现在的旅行成本)，以便我的算法能够支持迷宫中的多个目标。基本上，我想找到通过迷宫中所有目标的最短路径。为了确保路径是最优的，假设我们忽略了问题中的一致性，启发式函数需要是可接受的。
我知道这就像旅行推销员问题，但现在我只处理相对少量的数据，所以我想继续使用A start算法。
欢迎任何想法。谢谢!
浏览 10提问于2016-09-21得票数 0
回答已采纳
2回答
有约束的最短路径
、、、
我希望执行以下最短路径查询：
START source=node:myIndex(name="<src>"), destination=node:myIndex(name = "<dst>")
MATCH p = shortestPath(source-[:REL1*..5]-destination),
source-[sourceRel:REL1]-m,
浏览 1提问于2013-07-13得票数 0
回答已采纳
1回答
假设我有一个有向的加权图，有正的或负的权重，(没有零权重或负权重环)。该图是Bellman-Ford分析的，这意味着每个顶点都包含从源顶点到它的最轻路径的数据，以及它在最轻路径中的前身数据。存储从源到每个顶点的不同最短路径数量的最有效方法是什么？如果可能的话，我愿意把它做成线性时间O(V+E)。
浏览 4提问于2015-05-13得票数 1
8回答
这就是问题：
我有n个点(p1，p2，p3，..pn)，则它们中的每一个都可以以确定的成本x连接到任何其他节点。
每个点都属于一组点类型之一(例如"A“、"B”、"C“、"D"...)。
该方法的输入是我想要遵循的路径，例如"A-B-C-A-D-B“。
输出是连接我在输入中给出的类型的点的最短路径，例如" p1 - p4 - p32 - p83 - p43 - p12“，其中p1是A类型，p4是B类型，p32是C类型，p83是A类型，p43是D类型，p12是B类型。
“简单”的解决方案包括计算所有可能的路径，但计算成本非常高！
有人能找到
浏览 2提问于2009-07-17得票数 10
请花点时间了解我的情况。如果不能理解，请在评论中告诉我。
我有一个路径点的ArrayList。这些路径点没有任何顺序。路径点具有以下属性：
{int type, float z, float y, float x, float rotation}
这适用于三维世界，但由于我的路径发现不应该关心高度(因此将世界视为二维世界)，y值被忽略了。轮调对这个问题并不重要。
在这个二维世界中，x代表x轴，z代表y轴。
如果x增加，世界上的物体就会向东移动。如果x减小，世界上的物体就会向西移动。
如果z增加，世界上的物体就会向北移动。如果z减小，世界上的物体就会向南移动。
因此，这些“新
浏览 3提问于2011-03-04得票数 2
回答已采纳
1回答
有约束的弗洛伊德·沃尔
、、、
我想知道是否可以使用具有约束条件的floyd warshall，这意味着您有一组大小为logn的“特殊顶点”，并且您想要计算所有最短路径，但是每条路径必须至少经过一个“特殊顶点”，这是可能的还是很难的np？
浏览 5提问于2020-12-23得票数 2
回答已采纳
4回答
假设我有一组散落在XY平面上的点，我有两个点，即开始点和终点，在XY平面上的任何位置。我想找出起点和终点之间的最短路径，而不触及零散点。路径必须保持一定的偏移量(即假设路径有一定的宽度)。如何在编程中解决这类问题，机器学习中是否有算法？
浏览 12提问于2017-09-06得票数 0
回答已采纳
我想要计算所有N个节点对之间的最短路径(每个节点都有大约3个有向边)。重要的细微之处是，如果距离大于某个阈值(T)，我不再关心它(就我而言，D_ij>T=∞)。
因此，一旦我确定从i到j的距离大于阈值，我就不再需要继续寻找确切的值，只是为了知道它大于阈值。
是否已经有了一种包含这些阈值信息的最短路径算法来提高进程的效率？
请注意，对于所有D_ij <T的情况，我都关心D的确切值。
浏览 2提问于2015-12-07得票数 0
回答已采纳
1回答
我正在尝试开始一个我已经集思广益了几年的个人研究项目。我知道一些图表和算法，它们可以找到最快时间访问位置的最佳顺序。然而，我被困在我的研究的下一步，有没有研究论文/算法可以解决这个问题？给定一个起点和一个终点，其中有许多必须访问的“路点”。有些航点有时间限制，比如航点3必须在下午4点前到达。因此，算法必须首先根据位置的时间限制(如果有)对位置进行排序，然后找到访问每个路点的最佳顺序。
我已经研究了许多不同的算法/启发式方法，我已经搜索了关于这个主题的研究论文，但我找不到任何明确的东西。
提前感谢您的帮助。
浏览 0提问于2012-09-27得票数 2
如何在2D矩阵中找到从左上角到右下角的最小路径，计算成本，我们可以从北、南、东、西方向穿越。
浏览 3提问于2016-07-06得票数 1
回答已采纳
1回答
我使用下面的dijkstra实现来计算无向图中的所有对最短路径。在调用calculateAllPaths()之后，dist[i][j]包含i和j之间的最短路径长度(如果没有可用的路径，则为Integer.MAX_VALUE )。
问题是我的图的一些顶点是动态删除的，我应该从头开始重新计算所有路径来更新dist矩阵。我正在寻找一种解决方案，通过在顶点从我的图中删除时避免不必要的计算来优化更新速度。我已经在寻找解决方案，我现在有一些算法可以做到这一点，例如LPA*，但它们似乎非常复杂，我猜一个更简单的解决方案可能会解决我的问题。
public static void calculateAllPat
浏览 1提问于2015-12-25得票数 0
3回答
我正在尝试实现Dijkstra的算法，它可以找到起始节点和结束节点之间的最短路径。在到达终端节点之前，有一些必须通过的中间节点(多个)，例如，两个或三个必须通过节点，这些节点必须在到达端节点之前经过。
如果我有一个必须传递节点，我找到的解决方案是找到两个不同的路径，从必须传递节点到目的地，从必须传递节点到启动节点。
我想不出如何实现这样的算法。有什么建议吗？
谢谢。
List<Node> closestPathFromOrigin = null;
double maxD = Double.POSITIVE_INFINITY;
double _distance = 0;
int t
浏览 3提问于2014-08-18得票数 3
回答已采纳
我一直在尝试创建一个jQuery代码，它可以扫描包含id map和.map的div，并找到从#A到#B的最短路径，同时避免交叉/触摸#blockings，但我不知道如何做后者。
任何帮助都是非常感谢的。
插图：
，这是我的代码
computeTrack('#a','#b', '#map');
function computeTrack(A, B, MAP){
var bag = [];
var obstacle = [];
bag = getDistance(A, B);
obstacle = scanni
浏览 1提问于2015-12-16得票数 4
回答已采纳
2回答
我正在看一个关于负面循环的讲座。
在5:00，教员描述了假设不存在周期的情况。然后他说，任何一条路径都不会包含一个循环，因为如果一条路径存在于一个循环中，人们就可以显示一条没有循环的较短的路径，而这个周期可能只有非负的。
有人能帮我理解这一点吗？我好像听不懂。
谢谢。
浏览 10提问于2014-01-01得票数 1
回答已采纳
1回答
鲍勃和艾丽斯合作参加了一场游戏节目。在赢得第一轮比赛后，他们现在可以进入一个隐藏的金牌迷宫。如果鲍勃能收集所有的金币并把它们送到爱丽丝的位置，他们就可以把金子分开。鲍勃可以水平或垂直移动，只要他呆在迷宫中，而且细胞不会被阻塞。迷宫由n×m数组表示。每个单元格都有一个值，其中0是打开的，1是阻塞的，2是用金币打开的。Bob从(行，列)= (0，0)中单元格的左上角开始。爱丽丝的位置是由(x，y)决定的。确定the.shortest路径鲍勃可以按照收集所有金币，并交付给爱丽丝。如果鲍勃不能收集所有的金币，那就归还-1。
制约因素:-
1<=n，m<=100
金币0<=no <
浏览 4提问于2020-06-03得票数 0
1回答
在隐马尔可夫模型中找到最有可能的隐藏状态序列。我目前正在使用编写的以下非常棒的代码。
import numpy as np
def viterbi_path(prior, transmat, obslik, scaled=True, ret_loglik=False):
'''Finds the most-probable (Viterbi) path through the HMM state trellis
Notation:
Z[t] := Observation at time t
Q[t] := Hidden
浏览 1提问于2019-07-28得票数 11
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
我正在尝试找到与我有他的id的节点最近的具有特定标签的节点。
MATCH (object{id:'1489751911095'}), (apiUser:ApiUser) ,
p = allShortestPaths((object) - [*] - (apiUser)) return p limit 1
由于某些原因，它不会在第一次遇到节点apiUser:ApiUser时停止，而是会继续下去。
浏览 0提问于2017-03-18得票数 0
1回答
我试图使用python中的PuLP包实现最短路径问题的ILP公式。输入是使用NetworkX包生成的图形。
import networkx as nx
import pulp
import random
import matplotlib.pyplot as plt
g = nx.to_directed(nx.barabasi_albert_graph(20, 2))
# nx.draw(g, with_labels=True)
# plt.show()
source = 0
target = 13
dict_d = {}
for i, j in g.edges:
dict_d[i
浏览 1提问于2018-02-11得票数 1
回答已采纳
我的问题就像标题一样。在计算图的最短路径时，经常使用名为relax的操作。很容易理解为什么要使用这个操作，但是这个名字的含义对我来说是个谜。“”的意思是什么？
下面是用伪代码编写Dijkstra的示例：
DIJKSTRA(G,w,s)
1 INITIALIZE-SINGLE-SOURCE(G，s)
2 S ← Φ
3 Q ← V[G]
4 while Q≠Φ
5 do u EXTRACT-MIN(Q)
6 S ← S∪{u}
7 for each vertex v∈Adj[u]
8 do RELAX(u，v，w)
rela
浏览 6提问于2016-06-11得票数 3
回答已采纳
我想使用NetworKX和OSMnx生成一条始发地和目的地之间的路由。 原点是绿点，黑点是目的地。 我的约束是蓝色的圆圈，这是我必须经过的位置，抛出他们的区域。 ? 我的想法是找到从原点到第一个蓝色圆圈的最短路径，从第一个圆圈到第二个圆圈，等等。但我不知道如何让程序决定哪个将是第一个蓝色圆圈。 我想计算每个蓝色圆圈到原点的路线，但在有很多蓝色圆圈的情况下，这可能需要大量的计算。关于如何选择第一个或重建起点和目的地之间的轨迹，有什么想法吗？
浏览 14提问于2019-12-28得票数 0
1回答
我一直在阅读解决旅行商问题的不同算法，但似乎找不到一个不希望访问图中所有节点的示例。例如，假设我有一个由节点n1、n2、n3、n4、n5、n6组成的图。在经典的旅行商问题中，我希望在尽可能短的时间内访问所有节点。但是，如果我想离开n1，只访问n3 n5和n6怎么办？如果有必要的话，我可以通过其他的点头，但我唯一绝对需要访问的是n1、n3、n5、n6和n1。这意味着我要寻找的是经过这3个点的从n1到n1的最短路径。任何关于查看哪种算法的提示都是受欢迎的。
谢谢
塞缪尔·贝尼塔
浏览 0提问于2014-12-14得票数 1
2回答
我有一个有向无环图，需要找到有资源约束的最短路径。我的限制是所选择的路径必须具有最小数量的设置资源消耗。
目前，我正在使用计算K个最短路径，然后只接受那些满足我的约束的路径。这里的问题是猜测K，如果它被错误地选择，就有可能找不到可行的路径。
我已经找到了相当多关于这个主题的文献，我认为提供了一个很好的概述。然而，我正在努力理解它，并找到一个能够实现的简明算法(我正在使用Python，但是任何清晰的算法想法都会很好)。
我知道这个问题是NP完全的，因此我对任何好的近似算法以及精确的方法都感兴趣。
有人有什么好的建议吗？
浏览 1提问于2011-12-31得票数 3
回答已采纳
我有几个节点(无向图，双向图) ...每两个节点都有一个距离...
1-如何使用QuickGraph创建该网络?2-计算两个节点之间的最佳最短路径的正确算法是什么(考虑到之前可能会传入其他节点，例如:最佳路径A->B，传入C和D)
谢谢
浏览 3提问于2010-03-04得票数 2
回答已采纳
1回答
最小延迟图算法
、、、、
我需要关于图形问题的帮助。我正在寻找和现有的解决方案或算法，而不是实现我自己，如果有一个，请帮助我。我试过谷歌搜索但没有成功。
我的问题是:我有几个地点要参观，而且每个地点都有最后期限。通常情况下，我永远都无法访问他们，而且总是超过最后期限。我也有有限的时间去看望他们，例如每天8小时。我正在寻找一种算法，可以达到最小延迟后，交易。例如，我有位置A，B和C。位置A延迟1h30，位置B和C各延迟1h。如果我去地点A，我不能访问地点B和C，但如果我访问位置B，我可以去地点C，反之亦然。算法应该告诉我“去B和C"，因为然后我要从我的列表中删除一个2小时的延迟，并且只保留1小时30小时的延迟到下
浏览 2提问于2014-11-02得票数 0
回答已采纳
1回答
我需要一种在有向图中找到第二最短路径的方法，在第二最短路径的顶部不能完全包含最短路径。我知道dijkstra algoritm算法，但我无法想出一个简单的方法来改变算法，让我在合理的时间内获得第二短路径。算法，子代码或c++示例，三者之一将非常感谢。
浏览 3提问于2016-06-12得票数 2
1回答
给定G=(V，E)，即每条边都有这三种颜色(绿色，红色，蓝色)中的一种。如果一条路径包含所有三种颜色，我们称其为“有色路径”。
Input: graph G(V,E),weight function w:E->Q+ , colored edges and vertices s .
output: algorithm that finds for every vertices v, a shortest path from s
that is Colored path
我的解决方案是遍历该图，并为每个顶点计算路径具有的颜色数量。创建名为G1、G2、G
浏览 16提问于2017-01-30得票数 2
回答已采纳
11回答
图中节点之间的最短路径可以通过几种算法(Dikstra，A-star等)找到。
但是这个问题有哪些应用程序呢？(我已经知道了相当多，但我希望看到更多的例子)。
请仅提供一个应用程序/答案！解释应用程序，以及如何将其转换为最短路径问题。
浏览 0提问于2010-12-11得票数 13
2回答
用A*算法求几条最短路径
、、、
我正在制作一个路由应用程序，它使用A*算法来查找路由。我想提供的不只是一条路线，还有几条替代路线。例如，仅比最佳路由稍长一点的路由。
由于A* (和其他许多)只找到一条路线，我如何搜索这些替代路线？我应该使用其他算法吗？
浏览 0提问于2015-02-26得票数 1
2回答
有一个网格G。G(i，j)=-1表示路径阻塞。否则G(i，j) = (i，j)处的硬币数。
始终从起点起点(0,0)到达终点(n，n)，然后返回到起点(0,0)。一旦任何地点的硬币被收集起来，就不能再收集了。但是，您仍然可以拥有通过该位置的路径。
如果你可以在上、下、左、右的方向上移动，你最多能收集多少枚硬币？
我知道如何获得最大数量的硬币，当你只需要使用递归从(0,0)到(n，n)，但不能跟踪我已经收集的硬币从开始到结束。
请建议一个好的方法或参考一些资源。
浏览 20提问于2019-11-11得票数 0
给定有向JUNG图的两个节点A和B，我想确定从A到B是否有多条路径(不一定是最短路径)。
我只能想到两种方法，两种方法都很费时。
检索连接两个节点的所有路径(问题)，并检查是否有多个节点。
使用类DijkstraShortestPath检索最短路径，然后中断该路径并再次搜索最短路径。如果仍然有一条，那就意味着有多条路径。请注意，这也需要克隆图形，因为我不想更改原始图。
我怎样才能更聪明(也就是更快)做到这一点？
浏览 1提问于2013-04-05得票数 0
回答已采纳
基本最短路径问题和最短路径问题有什么区别？
一个最短路径问题，通过在图中找到从源节点到目标节点t的最短路径来解决。
一个简单的最短路径问题，通过在图中找到从源节点到目标节点t的最短路径，使得最短路径上的每个弧最多使用1次。
什么是基本的最短路径？
浏览 3提问于2020-03-19得票数 1
回答已采纳
我想找一个图中2个顶点之间的下一条最短路径，并且这条路径有一个正的cost.The，下一条最短路径是允许共享边的最短路径，我可以使用.Which算法吗？
浏览 0提问于2011-02-12得票数 20
回答已采纳
我的问题是：
我有一个无向图。每条边都有一个成本(或重量)。其中一个节点被标记为S。我想从S开始，至少访问每个节点一次。允许多次访问节点。允许多次沿边缘旅行，尽管这将使解决方案更加昂贵--以3倍的成本沿边旅行将使整个路径的成本增加6倍。这个图有一些“死胡同”的节点，所以有时我们不得不不止一次地遍历一个边。
什么是快速算法来做到这一点？这是一个众所周知的问题吗？
我要找的是：
相当快--我们这里讨论的图的相对大小是40-50个节点的顺序。所以这个算法希望不会超过10-15秒。
合理的最优--我不是在寻找绝对的最优性。任何有趣的启发式引导搜索，以使解将接近最优是足够好的。
我将用python写这篇
浏览 3提问于2012-09-05得票数 4
2回答
最长简单路径
、、、、
因此，我理解在图中寻找最长的简单路径的问题是NP困难的，因为您可以通过将边权重设置为1并查看最长简单路径的长度是否等于边的数量来轻松地解决哈密顿电路问题。
我的问题是:如果你得到一个图，找到最大边权重m，用m - w替换每个边权重w，并在上面运行标准的最短路径算法，你会得到什么样的路径？这显然不是最长的简单路径，因为如果是，那么NP = P，我认为这样的东西的证明会更复杂=P。
浏览 0提问于2009-04-04得票数 9
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
云直播活动推荐
腾讯云开发者
