非加权无向图中最短路径长度增加的边数最少算法
给定一个无权无向图的邻接矩阵，是否有一种有效的方法（多项式算法）来扩展或增加任意给定的两个结点s和T之间的最短路径长度？
示例：
在下面的例子中，从顶点S=1到顶点T=5有5条不同的“最短路径”，每个路径的长度为3。我想去除最少的边数，这样最短的路径长度被迫变成4或更多。（断开图形连接是可以的。）
0 1 0 0 0 1 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0 1
0 1 0 0 1 1 0 0 0 0 0
0 0 1 1 0 1 0 0 0 0 0
1 0 0 1 1 0 0 0 1 0 0
1 0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 1 1 1 0 0 0
1 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
表示此图形：
强制最短路径长度从3增加到4的最小代价是去除两条边（1,2）和（5,9）
目标：
共有1个答案
输入:G=(V，E)，顶点s，t和正整数D。
问题：最小化需要删除的边数，使dist(s，t)>=d。
这个问题对于d>3是NP难的，对于d的其他值是多项式可解的。
问题是在距离d和允许删除的边数上FPT参数化的，k:算法如下：找到一条长度最多为d的(s，t)-路径，并在d条边上分支，可以删除。这导致一个算法在O(d^k*n^2)时间内运行。
当仅用d（仅用k）参数化时，它是准NP-完全的（如W[1]-硬）。
参考文献:《有界长度的路径及其割：参数化复杂度与算法》，Golovach,P.A.和Thilikos，D.M.，《离散优化》第8卷，第1号，第72-86页，2011年，出版商Elsevier。
-
给出了一个图G=(V，E)，它是正加权的，有向的，无圈的。我设计了一个在O(k(m+n))中运行的算法，用于报告从s到T的k-边最短路径。k-边最短路径定义为从s到t的具有k条边的路径，并且对于从s到t的所有路径，该路径的总权也必须是最小的。 由于BFS不能单独用于寻找最短路径（除非权重相等），我认为运行时间意味着使用BFS寻找具有k条边的路径。让我感到困惑的是k，因为我认为它意味着表演BFS k
-
在一个加权有向图中，我需要找到两个结点s，t之间的最短路径。以下是限制： 权重可以为负值。 路径必须经过一个特定的边，让我们从节点u到V调用her e和shes。 输出路径必须简单，即我们只通过一个节点一次。 因为我希望它最短，所以我将检查在从s到u之前从v到t运行bellman ford是否比相反的方式更快（如果有节点，两个节点都使用where是放置它的最佳位置）。 谢谢你的帮助！
-
我试图将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写下我的想法来重申这个问题，我希望从你们那里得到一些反馈。谢谢 我的想法：对于每个叶节点，找到从根节点到它的最长路径。对于所有路径，找到最大路径长度 然而，这不就是蛮力吗，对此还有更优雅的解决方案吗？ 我听说过使用Djikstra的负权重算法，但在某些地方它说这只适用于特定情况？我也看到了关
-
我知道Bellman Ford算法使用负权值，但我希望我可以修改我现有的最短路径方法。
-
我遇到了一个问题，我必须找出给定图形中的最长路径。我有一个边列表（例如，{AB，BC}），它表明在顶点/节点（A，B，C）之间有一条边。现在我想计算出可能的最长路径（不重复顶点），这样它可以覆盖从任何顶点/节点开始的最大节点。 解决这个问题的最佳方法是什么？我必须把它作为一个计划来实施。 我在谷歌上查找最小生成树、Dijkstra的算法等等。但我想不出什么最适合解决这个问题。 任何帮助或阅读参考资
-
在无向赋权图中寻找两个顶点之间的最短路径。还已知权重是小于log（logV）的整数，其中V是顶点的数量。使用贝尔曼-福特或Dijkstra算法很容易解决，但是有没有什么算法可以更快地解决呢？ 到目前为止，我一直在考虑使用BFS，将权重大于1的边划分成两个权重为1的边，但如果V是大数，就不是一个好主意。不，这不是我的家庭作业，我只是在想。