4回答
假设我有一组散落在XY平面上的点，我有两个点，即开始点和终点，在XY平面上的任何位置。我想找出起点和终点之间的最短路径，而不触及零散点。路径必须保持一定的偏移量(即假设路径有一定的宽度)。如何在编程中解决这类问题，机器学习中是否有算法？
浏览 12提问于2017-09-06得票数 0
回答已采纳
1回答
图中的最短路径
、、
给定一个具有N (1 <N≤1000)个顶点和正权的无向图G。找出从顶点1到顶点N的最短路径，或者声明该路径不存在。
提示:在每个步骤中，在尚未检查的顶点中，找到从顶点1到它的最短路径的顶点，选择从顶点1到它的路径最短的顶点。
我在topcoder上发现了这个问题，我认为应该使用Dijkstra的算法，但这篇文章是关于动态编程的，而Dijkstra是一个贪婪的算法。
谁能告诉我解决这个问题的最好方法。
谢谢
浏览 3提问于2016-07-28得票数 1
2回答
用A*算法求几条最短路径
、、、
我正在制作一个路由应用程序，它使用A*算法来查找路由。我想提供的不只是一条路线，还有几条替代路线。例如，仅比最佳路由稍长一点的路由。
由于A* (和其他许多)只找到一条路线，我如何搜索这些替代路线？我应该使用其他算法吗？
浏览 0提问于2015-02-26得票数 1
1回答
假设我们在一个无向循环加权图中有一条路径。假设我们有一个引擎可以在这样的图中找到从节点A到节点B的路径，有没有一种简单的方法/算法来计算出从A到B的给定路径是否比从A到B的任何其他不相交的路径至少好X%？我所说的不相交是指两条路径不能共享任何边。
浏览 1提问于2011-10-08得票数 1
回答已采纳
我有一个表单的输入文件：
London Birmingham 117
Birmingham Bristol 85
London Oxford 56
San_Francisco San_Jose 50
San_Jose Davis 270
San_Francisco Davis 350
END OF INPUT
(实际文件有更多的节点)我必须使用不知情的搜索算法找到两个输入城市(命令行参数)之间的最短路径。到目前为止，通过以下方法制作了一个图(列表)：
Graph = {}
filename = open('Input1
浏览 1提问于2015-09-05得票数 1
1回答
有没有人知道我如何编写一个编程的图算法(C++代码会很棒)，它可以为循环图中给定的一组节点和边找到第k条最短路径？
例如，最短路径(可以由Dijkstra或Bellman Ford找到)被认为是第1个最短路径。现在第二个最短路径是位于第一个最短路径之后的最短路径。现在我想让算法找到第k条最短路径。给定节点、边和边集的数量，如下所示：
节点数:5
边数:6
边缘：
0 1
0 2
1 2
2 3
3 1
1 4
源节点:0
目的节点:4
“请注意，此图包含一个循环”谢谢。
浏览 0提问于2012-02-20得票数 1
回答已采纳
7回答
我已经学习了一种动态编程算法，它可以找到从A到B的“最便宜”路径。每条子路径都有一个相关的成本。
每个角的计算方法是
D(i,j).value = min( (D(i-1,j).value + D(i,j).x), (D(i,j-1).value + D(i,j).y))
其中x和y是节点左侧和节点下方的路径的成本。
我现在很难在最好的时间内计算出可能最便宜的路径数量。
有什么建议吗？
浏览 0提问于2010-02-05得票数 2
回答已采纳
1回答
给出了一个加权无向图G和两个顶点a，b，我们要找到两条路a -> b和b -> a，使得它们不共享任何边，使得两条路中的边权和最小.可以有多达1,000个顶点，以及最多可达10,000边。
我最初试图想出一种动态编程方法，但却找不到。如有任何想法/建议，将不胜感激。
浏览 4提问于2012-08-09得票数 5
回答已采纳
1回答
我是编程新手，我遇到了一些问题。基本上，我必须创建一个函数，它将通过网络图找到所有路径的长度。我已经为此工作了几个小时了，但我似乎什么也没做。使用递归，我可以浏览每条路径，但我只是不确定应该如何记录路径的长度。
任何帮助都将不胜感激。谢谢!
编辑:更多信息。依赖关系数组是网络上每条路径的依赖关系。路径6链接到路径4和2，路径5连接到路径3，等等。持续时间是每条路径花费的时间，所以路径6需要10个小时，路径5将需要9个小时，等等。
不具有依赖性的路径1、2和3从起点扩展，并且不依赖于所有的路径5和6会聚到终点。所以我必须找出所有路径从开始到结束的持续时间。到目前为止，我采取的方法是从终点到起点，
浏览 1提问于2010-05-09得票数 1
3回答
全对最短路径，领带断裂
、、、
我正在创建一个程序，它将计算未加权图中所有节点的Betwenness中心性。要做到这一点，我必须找到ASSSP (所有单一源最短路径)。在创建程序时，我意识到最终我将有联系(从源到目的地的距离相同，但路径不同)。这使我想到了这个问题。我该如何解决这些关系？如果我使用随机的断线器，那么对于相同的输入，中间中心度的每个输出可能略有不同。让我做一个小小的示范性图：
A
/ \
B C
\ /
D
现在假设A节点是我们希望找到ASSSP的源。可见，有两条路径(A->B->D和A->C->D)，bot的长度相同，两者最短。现在我应该选择哪一个，在什么条件
浏览 2提问于2012-07-11得票数 2
回答已采纳
2回答
图中两个顶点之间的最短路径
、、、、
我必须做下面的任务：“你有一个图G(V，E)和它的顶点x和y的to。写一个程序，找到两个顶点之间的最短路径，根据顶点的数量。
我不知道是否该由我来决定这个图是否是有向的，或者我是否应该有一个边类，或者是什么类型的图实现。这是我的书(java编程入门)“树和图”一章中的第一个练习，我不知道从哪里开始。你会怎么做?为什么？
浏览 2提问于2015-05-25得票数 0
我目前正在研究Bellman算法，出现了一个疑问。据我所知，Bellman算法从它的来源创建最短路径，如果图中有一个负循环，它返回true，算法停止，另一方面，它用最短路径返回false。
我现在的问题是，该算法是避免了图中创建最短路径的正循环，还是没有考虑到它们(因而落入了它们的陷阱)？
提前感谢！
浏览 4提问于2022-01-12得票数 1
回答已采纳
3回答
我很难理解的用处。我认为这个问题对于一个在这个领域有知识的人来说听起来一定很愚蠢，但我想不出来。根据维基百科，Johnson算法使用Bellman Ford算法将边的权重转换为非负权重，然后使用Dijkstra算法查找最短路径。但贝尔曼·福特算法也是一种寻找最短路径的算法。为什么我们不使用从贝尔曼·福特算法得到的最短路径呢？
浏览 0提问于2011-03-16得票数 4
回答已采纳
2回答
我不确定我在这里是否使用了正确的术语。我试图想出一个算法，让我们在任意图中找到一个顶点，这样顶点与最远顶点的距离最小。
另外，我还想出一个算法，让我找到两个顶点，而不是一个，再把最远的顶点到这两个顶点之间的距离最小化。
我的直觉说，我应该想出一个算法，计算出图中所有顶点之间的最短路径，然后查看路径，找到流量最高的顶点。但是我很难想出一个具体的算法，因为我以前根本没有这方面的经验。我试着用谷歌搜索这个问题，但没有成功。如有任何指导，将不胜感激。
浏览 0提问于2016-11-01得票数 -2
回答已采纳
1回答
我正在看。
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
// part 1
for each vertex v
dist[v][v] ← 0
// part 2
for each edge (u,v)
dist[u][v] ← w(u,v) // the weight of the edge (u,v)
// part 3
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
浏览 2提问于2013-06-03得票数 0
回答已采纳
我目前正在研究非负边权图中的最短路径问题。
我知道Dijkstra算法可以给出单源最短路径问题的解决方案，也就是可以找到从一个节点到所有其他节点的最短路径，但是我还没有找到算法，可以给我一个先验的更简单的问题:找到两个节点之间的最短路径。
直觉上，我认为可以找到例子，表明“简单”问题并不比单源最短路径问题更简单，但我正在寻找参考资料，在简单的图(即有几个节点)上显示这种矛盾(先验)。
浏览 4提问于2022-05-11得票数 2
1回答
如何在图或ANN中引导信息流？
、、、、
我正在构建一个无方向的ANN。没有不同的输入或输出节点，并且所有连接都是无定向的。
为了使网络工作，我正在设计系统，将每个节点的动作阈值和加权关系视为其到“焦点”节点(临时输出节点)的距离的函数。
换句话说，我将任意选择一个或一组节点作为数据的端点和输出。此节点可以随时更改。流经图形的信息流将像磁铁一样吸引所选节点，因为从统计上讲，靠近末端节点的节点更有可能激活并沿该路径发送信息。
我希望这可以创建一个非常动态和现实的ANN模式，具有非常准确的学习模式。
现在，我被困在如何有效地确定每个节点到末端节点的距离的问题上。据我所知，如果我使用Neo4j，平均需要大约250ms来计算两点之间的最短路径
浏览 0提问于2011-07-30得票数 2
回答已采纳
1回答
是否可以使用Dijkstra's Algorithm计算从单个源到单个目标的N条最短路径，其中N是节点数？我知道Dijkstra从一个源输出到图中所有节点的最短路径，但当我正在读一篇研究论文时，作者提到了使用Dijkstra计算s和t之间的N条最短路径，这让我有点困惑。
以下引用原文：利用基于SDN的SCADA系统:一个反窃听的案例研究-也发现了
Dijkstra的算法22用于计算N个阶段的最短路径(步骤5)。考虑N= 2，在第一阶段，Dijkstra算法确定了两个网络设备之间最短的路由，从而使所有链路开销的权重增加了10倍。紧接着，在第二阶段(并且随着链路成本的增加)，Dijkst
浏览 0提问于2015-11-25得票数 2
回答已采纳
2回答
我试图研究平面上两点之间的短路径的不同算法。
我发现的绝大多数算法使用离散映射(网格映射、可见性图、Voronoi路线图等)。
有些书(如Ben的“机器人元素”或Nikolaus的“自主机器人简介”)提到了连续地图(例如原始多边形数据)，但没有解释相应的算法。他们声称记忆或效率优势的少数和简单的障碍，这可能是非常有趣的。
我认为，应该有一个聪明的方法，使用几何计算(例如，交叉检测)和一些算法范式(例如，最小成本分支和界)，但我不想糟糕地重新发明车轮。
是否有任何资源用于使用连续映射或有用的关键字来搜索短路径算法？
像建议的那样，我试图指定我使用的一些术语：
连续映射
指
浏览 6提问于2020-08-19得票数 1
回答已采纳
如何使用Floyd-Warshall算法获得从顶点1到顶点10的每条具有相同权重的最短路径？我设法得到了从顶点1到顶点10的所有最短路径的总数。
public static int[][] shortestpath(int[][] adj, int[][] path, int[][] count) {
int n = adj.length;
int[][] ans = new int[n][n];
copy(ans, adj);
// Compute incremently better paths through vertex k.
for (i
浏览 5提问于2018-04-18得票数 3
1回答
你好，我有一个与动态编程相关的问题。如何计算从起始节点到终点的跳数中的最短路径，约束顶点和边具有相等或更高的预定义值。例如，网络中数据的最高速率。有人能提供一些伪代码或任何想法吗，谢谢。
浏览 3提问于2022-06-09得票数 0
1回答
我的理解是，BFS和DFS是图遍历算法，而其他算法(如A*和dijkstra )则用于在图的两个节点之间寻找最短路径。但是在一些地方，我认为BFS和DFS也被称为最短路径查找算法。请详细说明图遍历算法与最短路径查找算法的区别。谢谢!
浏览 6提问于2022-05-06得票数 0
2回答
我想知道是否有一种算法可以在图中找到最短路径。
假设我有一个图，从一个顶点到另一个顶点有一对路径。这些路径中的两条或更多条具有相同的成本。如何标记、查找这些顶点之间的所有最短路径？据我所知，Dijkstra或Bellman-Ford算法会找到最短路径，但他们只“选择”一条。
浏览 1提问于2010-08-09得票数 1
回答已采纳
Shortest Path算法与Djikstras Algorithm算法和Travelling Salesman算法有什么区别？据我所知，在Shortest Path中，我们不会通过所有最短路径的顶点。在Travelling Salesman Problem中，我们只遍历所有顶点一次。关于Djikstra's Algorithm，我学到的和旅行的推销员是一样的。但视频教程()却有不同之处。
请解释一下。
浏览 8提问于2014-10-16得票数 1
回答已采纳
1回答
我有一个三角形矩阵NxN表示顶点之间的距离(顶点我只与向量j>i连接)，我想从第一个到最后一个对路径进行采样，并使用它作为训练样本。有算法来做吗？在A*中交换min->样品是否足够？
浏览 0提问于2020-01-13得票数 2
4回答
使用下面的代码，我试图找到第二条最短路径/第k条最短路径.
// Run Dijkstra's algorithm on given graph
public static void shortestPath(GraphModel graph, int source, int destination, int numberOfVertices)
{
// create min heap and push source node having distance 0
PriorityQueue<NodeModel> minHeap
浏览 0提问于2019-07-17得票数 1
1回答
我需要在下面的图中计算从A到B的两条路径，约束条件是这些路径不能共享任何边：
嗯，好吧，不能上传图片，这是个。
所有的边都有正权重；对于这个例子，我认为我们可以假设它们是相等的。我的简单方法是使用Djikstra的算法来计算第一条路径，如上图中的第二张图所示。
然后，我从图中删除边，并尝试计算第二条路径，但失败了。有没有Djikstra，Bellman-Ford (或其他任何东西)的变体，可以计算上面第三张图中显示的路径？(我的意思是，不需要特殊知识，也不需要删除转载链接)
浏览 0提问于2010-05-11得票数 0
1回答
只要想一想下面的一个算法就可以了。
给定一个矩阵，每个节点都有一个值。您从0,0开始，并且必须到达n,m。在i,j中，您可以转到i+1,j或i,j+1。当您踩到每个块时，该块上的值将添加到您的当前分数中。你必须携带的最低初始分数是多少，这样你才能始终到达n,m(通过任何可能的路径)，并在结束时获得正分数。
例如：
Matrix -> 2 3 4
-5 -6 7
8 3 1
Ans -> 6-对于路径2、-5、-6、3、1，我们需要初始分数为6，这样当我们到达1时，我们的正分数为1
浏览 0提问于2016-04-03得票数 1
1回答
我刚学过图论，需要一点帮助。假设我们有一个具有定义的开始和结束版本的图。如何使用BFS只得到起点和终点之间的最短路径。
我已经编写了一个计算整个图中最短路径的程序，但是当我想要将树限制在起始端之间的这些顶点时，我不知道如何实现它。
任何帮助，伪代码，建议将不胜感激。
浏览 8提问于2013-12-23得票数 1
回答已采纳
给出了具有n顶点和m弧(n <1 500，m<5 000)和一弧(u，v)的有向加权图.回答的问题是，有多少条最短路径(可以从a的任意位置开始，以b结束，以便a！= b)通过给定的弧。
示例：
N= 4，m=4
弧(1，2)的重量为5
弧(2，3)的重量为5
弧(3，4)的重量为5
弧(1，4)，重量为8
和弧(1，2)。
答案是2，因为弧(1，2)在最短路径1->3和1->2。
迪克斯特拉能解决这个问题吗？
浏览 1提问于2018-10-26得票数 3
我不是要求一个算法来检查图中负圈的存在(Bellman Ford或Floyd Warshall可以这样做)，而是在图包含至少一个从源顶点可以到达的负圈，并且从负圈可以到达目标顶点的情况下，是否存在多项式时间算法来寻找两点之间的最短路径。
浏览 3提问于2013-09-02得票数 2
回答已采纳
3回答
启发式算法是如何工作的？
、、、
最近我正在学习一些启发式算法，比如A*搜索算法。我知道一些关于启发式搜索算法的基本事实，如f(n)=g(n)+h(n)，我也知道每种方法的可容许性和一致性。但让我困惑的是启发式算法是如何工作的？如果启发式值更接近成本的实际值，为什么会更好？谢谢!
浏览 8提问于2013-10-07得票数 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
2回答
我使用netwrokx计算不同顶点之间的最短路径，使用Dijkstra算法。我有一个例子，我想连接三个不同的顶点(例如，A，B和C在一个无向图中)。首先，我找到了从A到B的最短路径，然后我想要找到从A到B的路径的最短路径。到目前为止，我尝试的是从A到B路径的所有节点到C的最短路径长度，然后计算出从节点到给定最小路径长度的最短路径。这是计算密集型的，因为路径可能有多达200到300个节点。
有人能给我一个提示吗?我如何改进方法？或者更容易找到从已有的边缘到目标的最短路径？
浏览 1提问于2018-08-15得票数 2
回答已采纳
4回答
“弗洛伊德-沃尔”算法“和”Dijkstra的算法“”之间有什么区别，哪种算法是图中最短路径的最佳选择？
我需要计算网络中所有对之间的最短路径，并将结果保存到一个数组中，如下所示：
**A B C D E**
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0
浏览 20提问于2009-12-04得票数 27
回答已采纳
1回答
我有一个像加权迷宫一样的网格，我需要在没有任何关于迷宫的先验知识的情况下找到通向实体的最短路径。
像A* expect priot knowledge这样的算法在环顾四周时会“跳来跳去”，但当我有一个机器人的时候，这是不可能的。
我的第一个想法是最初使用BFS探索整个迷宫，然后在探索的迷宫上应用A*，以找到考虑权重的最短迷宫。但这似乎太天真了。
有没有人能给我一些适合这个问题的算法？
浏览 0提问于2018-12-10得票数 3
嗨，我在为这个问题而挣扎。其内容如下：
设计一种算法，在加权有向图G= (V，E)中求最小权环(即图中所有圈的最小边权和)。简要说明运行时和空间的复杂性。假设所有的边都是非负的。它应该在O时间内运行。提示:对Dijkstra的算法使用多次调用。
我已经看到了使用弗洛伊德-沃尔的解决方案，但我想知道我们将如何使用Dijkstra，以及如何在给定的时间限制内做到这一点。
我有几点困惑：
首先，我们如何知道图中有多少圈，以及如何检查这些循环？
还有，为什么会是E_？根据我的理解，你应该遍历所有的顶点，因此使它成为？
这是为了我的个人学习，所以，如果任何人有他们可以使用的例子，
浏览 4提问于2017-11-26得票数 0
我正在开发一个个人项目。在这个视频游戏中有一个基于网格的移动、创建和寻路系统。在此之前，我曾使用A*寻路来使某些字符移动到某个已知位置。
但现在我遇到了一个大问题。在我的游戏中有一个角色必须去一个特定的对象，但是这个角色不知道这个物体的精确坐标。最简单的方法是真正知道这些物体的坐标，计算出哪个是最近的，并使用A*路径查找来达到这个点，但是这种方法看起来确实是被操纵的，而且对我所做的游戏的类型来说还不够动态。
因此，我想知道是否有一些路径查找算法可以在某个点(正在使用该算法的字符的位置)附近搜索，比如以径向方式进行搜索，并一直搜索直到它找到正在寻找并返回到该特定对象的路径的对象类型。
浏览 7提问于2016-06-01得票数 0
回答已采纳
2回答
Dijkstra的最短路径算法会在具有负权边的有向树上返回正确的结果吗？
在具有负权重的一般图上，该算法将失败，但由于它是一棵有向树，因此感觉该算法会成功。
浏览 5提问于2022-06-01得票数 2
1回答
图算法问题给你。
我有一个图表，用来表示一个道路网络。因此，在它的循环(一个回旋将是一个微不足道的)。还有一些边缘是双向的，有些是单向的(单向街道).边是按长度加权的。
假设我有两个节点，并且已经计算了它们之间的最短路径。我想要做的是找到连接两个节点的所有其他路径，它们都比某个距离还要短。
下面是ascii技术中的一个例子，其中我用字母标记了边，用数字标记了节点。
F
5----6
E / \ G
3--------4
/ D \
B / \ C
1--------------2
浏览 3提问于2013-09-07得票数 0
回答已采纳
3回答
我目前正在优化电网规划，而MST没有很好地解决这个问题，因为如果到主电网的连接是一个辐射点，所有的电力都必须流经一条边，并将经过很长的“电气距离”到达每个耗电量点。
我正在研究的问题可能是最小化MW*distance或有功功率矩，但这会产生一个非线性问题。
所以我要找的是一个最小的生成树(不是最优的，只是最有效的)，它最小化到树根的最大电气距离(通过图的距离)。
通过这种方式，我只是购买更长更细的电缆，这是一种更便宜的解决方案，较短，较厚的电缆。
浏览 1提问于2013-06-27得票数 6
1回答
我有多个来自步行路线的gpx文件，我将它们组合成一个大的gpx文件，这样它就可以显示某个区域的所有路线的集合。我想在MATLAB中使用该文件，并在其上执行Dijkstra的最短路径算法。有谁能推荐一个这样做的方法吗？
我是否应该转换gpx数据以使其成为可能，或者是否有方法对数据本身进行这些计算？
浏览 7提问于2021-05-30得票数 0
众所周知，A星算法是完全的。然而，我发现搜索web的所有实现似乎只返回第一个(最佳)解决方案。
例如，这个实现：
由于算法总是以最小f值扩展节点，而且当第一个节点是解决方案时，实现似乎停止了，那么如何调整上述代码，从而输出所有(或第一个n)导致目标的路径，而不考虑重复的操作(即一次又一次包含相同操作的路径)？
浏览 2提问于2013-01-30得票数 1
我需要知道什么是最理想的旅行路径，每个人同时(假设4个小时)。这些人同时从A市开始(*见表)。
我有三个mysql表，如下所示：
表
people:
id name
1 People A
2 People B
3 People C
city:
id name
1 City A
2 City B
3 City C
... ...
26 City Z
distance:
fromCity toCity distance (km) time (appox. travel in minutes)
1 2
浏览 2提问于2020-04-20得票数 0
4回答
首先，我知道Dijkstra不适用于负重，我们可以用Bellman代替它。但是在一个问题中，给出了所有边都有从0到1的权重(0和1不包括在内)。路径的成本实际上是产品。
所以我想的是把日志拿走。现在所有的边缘都是负值。现在我知道Dijkstra不会对负重起作用，但是在这种情况下，所有的边都是负的，所以我们不能做一些事情，这样Dijkstra才能工作。
我想把所有的权重乘以-1，然后最短的路径变成最长的路径。
在这种情况下，我可以避免使用Bellman算法吗？
确切的问题是：“假设在某些应用中，一条路径的代价等于路径中所有边的权重的乘积。在这种情况下，如何使用Dijkstra算法?所有边的权重从
浏览 3提问于2015-04-18得票数 7
回答已采纳
我只有一个困惑，那就是在贝尔曼-福特算法中，我们运行n-1次，这是没有边的，而在Floyd warshall算法中，我们在每个阶段运行n次，所以在贝尔曼-福特的情况下，我们排除了源顶点，这就是为什么我们运行n-1次，我在这里与n和n-1有点混淆，请澄清这一点。
浏览 5提问于2015-12-25得票数 9
回答已采纳
我的问题是:假设我们有一个有向图
a->b (成本4) a->c (成本2)
b->d (成本1)
c->d (成本3)
所有的边都有离散的成本。从a到d有2条路径，成本都是5。会有2个最短路径树还是1个？
一般的问题是:假设我们有一个有向图，那么这个图有一个唯一的短节路径树？
这是一份委托书。
谢谢您抽时间见我。
浏览 0提问于2013-12-08得票数 0
4回答
寻找图中两点之间的最短路径是一个经典的算法问题，有许多好的答案(，等)。我的问题是，是否有一种有效的算法，在给定一个有向加权图、一对节点s和t以及一个值k的情况下，找到s和t之间的第k条最短路径。如果有多条相同长度的路径都与第k条最短路径相同，则算法可以返回其中任何一条路径。
我怀疑这个算法可能可以在多项式时间内完成，尽管我知道可能会减少，这将使其成为NP困难。
有没有人知道这样一种算法，或者说有一种约简表明它是NP-难的？
浏览 1提问于2011-08-27得票数 28
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议活动推荐
腾讯云开发者
