longest-path

    2热度

    2回答

    如何在图表中找到最长的简单路径？

    我知道，对于非有向图，这个问题是NP完全的，因此我们应该使用Brute Force来检查所有可能的路径。我们如何做到这一点？请建议一个伪代码，并告诉我该算法的复杂性。 如果有优化，那就太棒了！
    algorithm graph longest-path 2014-02-19

    1热度

    1回答

    查找树中一组节点之间的最长路径

    最近遇到一个编程问题。给定一棵树，可以是非二进制的，可以是单个链（或线性），具有N个节点。 输入将是一组K节点，表示为a1，a2 .... ak。 我想找到从这K个节点中的一个节点开始并在其中一个K节点（与开始节点不同）处结束的最长简单路径。 取决于N或K的对数算法应该满足运行时间要求（例如：KlogK，KlogN），如果需要的话应该在我想要的时间限制内。 谢谢
    algorithm data-structures tree longest-path 2013-03-09

    0热度

    2回答

    加权有向非循环图的最长路径

    我试图将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多答复者，所以我想通过写下我的想法来重申这个问题，我希望能够从你们那里获得一些反馈。谢谢！ 我的想法： 对于每一个叶节点 查找根节点到它 对于所有路径的最长路径 找出最大路径长度 然而，是不是这只是蛮力？有没有更优雅的解决方案呢？ 我听说过使用Djikstra算法的负权重，但在某些地方它说这只适用于特定的情况？我
    graph directed-acyclic-graphs longest-path 2012-12-05

    1热度

    1回答

    用于分层的最长路径算法

    我正在制作一个程序以生成公司的组织结构图。我一直在阅读最长路径算法来对顶点进行分层，并且有一件事情一直在困扰着我。我所做的阅读表明，图形应该从下到上进行分层，首先将底层没有子节点的节点放到底层，然后进行处理。不过，我也读过最长路径算法导致图底部非常宽。 我在想，我会尝试从顶部开始构建图表，从没有父母的节点开始，一路走下来。也许这是常见的，我只是没有看到它的使用，但我担心有一些原因，我没有看到这种做
    graph-drawing longest-path 2012-10-24

    0热度

    1回答

    如何计算此Q＆A流程的最短和最长路径？

    我有问答&像下面这样的流程： 的基本思路是，根据选择的问题的答案，不同的问题会接着问。 我目前代表这个问答&与以下JavaScript对象的流程： var QAndAObj = { 1: { question: 'Question 1', answers: [ { answerText: 'Answer 1-1', nextQues
    javascript json recursion shortest-path longest-path 2013-11-28

    3热度

    1回答

    使用R igraph加权DAG的最长路径

    我使用R igraph实现了加权DAG的最长路径计算。 我的实现（如下所示）对于大图很慢。 我会非常感激任何提示加快它的提示。 任何关于我的实现离最知名/典型算法有多远的想法也是值得欢迎的。 谢谢！ # g is the igraph DAG # g <- graph.tree(10000, 2, mode="out") # E(g)$weight <- round(runif(length(
    r igraph longest-path 2014-11-14

    -2热度

    2回答

    如何在有向循环图中找到最长的简单路径（包括所有中间节点）？

    我在这里搜索了如何在定向循环图中找到最长的简单路径（简单的意思是每个节点只访问一次，避免路径无限），并且遇到了像this这样的解决方案。然而，我发现的所有这些解决方案仅显示如何计算最长路径的长度，而不是该路径中涉及的实际节点。 因此，我的问题是如何修改像that这样的算法，以便提取最长路径中涉及的节点？类似于Floyd-Warshall所有对最短路径算法可能是modified to allow p
    algorithm graph-algorithm longest-path 2014-11-14

    0热度

    1回答

    从到一个最远的一个节点查找距离它BOOST

    我需要从所有节点的距离，它鳍节点最远的最小生成树。到目前为止，我已经完成了这项工作，但我无法找到距离节点最远的距离。 #include<iostream> #include<boost/config.hpp> #include<boost/graph/adjacency_list.hpp> #include<boost/graph/kruskal_min_spanning_tree.hpp>
    c++ boost c++11 nodes longest-path 2013-10-20

    0热度

    1回答

    直接非循环图中最长的路径

    如何在没有权重的情况下找到DAG中最长的路径？ 我知道如果DAG是拓扑排序的，从A到B的最长路径可以在线性时间中找到，但是我需要在所有图中找到最长的路径。有没有什么比搜索所有顶点对之间最长路径（这将是O（n^3））更快的方法？
    algorithm directed-acyclic-graphs longest-path 2013-04-07

    1热度

    1回答

    如何使用OGDF库在非循环有向图中找到最长路径？

    我是OGDF库的新手，需要在非循环有向图中找到最长的路径（我想使用内置函数的OGDF）。 我知道，有可能找到最长的路径使用负边权重为最短路径算法，但也找不到适当的函数。 OGDF有具体的功能吗？ 如果是，我该如何使用它？
    graph shortest-path longest-path 2012-08-02
最新问题