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
最新問題