那些遇到过的问题

如何找到最高成本的路径

Raf*_*ita 2 java graph-algorithm

我有一个有向图,其顶点有成本.我想在两个顶点之间找到最大成本的路径,但我只找到算法以最低的成本解决路径.

另外,我正在使用Java.

pai*_*lee 5

  1. 规范化所有成本,使最低成本大于0.
  2. 将所有费用更改为(1 /成本).
  3. 运行最低成本算法.

生成的路径是原始图表上的最大成本路径.

  • 线性复杂性很便宜.何必？ (2认同)
  • 我认为这是不正确的。考虑一个具有节点 A、B、C、D 以及以下边和边成本的图：A->D (1)、A->B (2)、B->C (2)、C->D (2 ）。假设我们正在寻找从节点 A->D 的路径；有两个选项：A->D，成本为 1 或 A->B->C->D，最大成本为 6。您的算法仍会输出 A->D 作为结果（因为 1/1=1）而不是 A->B->C->D（因为 1/2+1/2+1/2=1.5）。 (2认同)

归档时间：

查看次数：

380 次

最近记录：

8 年，2 月 前
相关归档
如何设置JDK Netbeans运行？ 203
为什么java.util.Optional不是Serializable,如何使用这些字段序列化对象 101
Java中的长度和长度() 85
将Hibernate Query.list()强制转换为List <Type>的"正确"方法是什么？ 80
为什么switch语句上有奇怪的缩进？ 68
indexOf区分大小写？ 67
使用Jackson进行映射时,将默认值设置为空字段 60
如何在Java中使用StringUtils？ 54
如何在Java中选择两个同名的方法 43
初始化和实例化的Java顺序 43
难疑归档
Flash CS4拒绝放手 2735
如何使用scp将文件夹从远程复制到本地？ 2562
什么是C ??!??!操作员呢？ 1911
如何在Node.js中退出 1762
我在哪里将'assets'文件夹放在Android Studio中？ 1366
漂亮的git分支图 1290
Markdown中的评论 1277
SQL仅选择列上具有最大值的行 1142
Visual Studio中的构建解决方案,重建解决方案和清洁解决方案之间的区别？ 1081
在Notepad ++中将制表符转换为空格 1042