最長路徑演算法

『壹』 圖中的最長路徑問題怎麼算

把距離取負值就是個最短路徑問題，有負權值的最短路徑不適用dijkstra演算法，但基於鬆弛技術的bellmanford和floyd演算法都是適用的，計算多點之間最短路徑使用floyd演算法
具體來說是進行n-2輪鬆弛，即對任意兩點窮舉第三點，並嘗試將距離替換成經由第三點的距離。完成後額外進行一輪鬆弛，如果距離繼續變小，說明存在負權有向環，最短路徑不存在（可以不斷沿著環繞），否則當前路徑就是最短路徑。

『貳』 數據結構AOE網最長路徑問題

圖中每個頂點表示事件，每條弧表示活動，從定義中也可以知道，最長路徑即是關鍵路徑，此圖可以表示一個工程的流程圖，一個工程的最早完成時間自然是工程中所有最花費時間的活動都已完成所花費的最長時間，因為工程中的某些子工程是可以同時進行的。大概就是這樣，如果要問這個18是怎麼求出來的，這個問題就難以解釋了，因為本身演算法就很復雜，不是幾句話就能說清楚的。上面這個圖是清華大學計算機系教授嚴蔚敏與吳偉民所合編的《數據結構（C語言版）》中的原圖，建議你搜索嚴蔚敏的視頻看一看，共48集，多看幾遍應該就沒什麼問題了

『叄』 數據結構：可以用求最短路徑的方法思想求最長路徑么

floyed演算法可以有迴路，但是不能有負權迴路。
最長路問題分成兩種：
1. 可以走重復邊。
2. 不能走重復邊。
如果是1的話，那麼如果圖中有一條權為正的環，那麼你沿著環反復走就得到無限長的路了，而如果沒有這樣的環的話，Bellman–Ford（單源）或者Floyed（任意點對）演算法都可以計算出正確的解。
2的話是NP-Hard。

『肆』 查找DAG中的最長路徑

首先要看DAG的數據是怎麼定義的

『伍』 請教無向無環圖最長路徑演算法

無向無環圖就是樹，
從根出發：
如果是計算最多的路徑，就用廣度優先（層次遍歷）就可以了，最後訪問的頂點一定是最多的路徑的
如果是計算最長的路徑長度，直接將上面的演算法改一下，每個頂點時記下前面的來路的值加上現在的，就可以求出最大值
或者直接用Dijkstra 演算法就可以了

『陸』 求一個最優路徑演算法的思路

同意樓上，最長路徑是NPC問題，不存在多項式演算法。

證明是簡單的：
1、最長無環路問題的判定版本是「給定有向圖D和整數k，問D中是否存在長度大於或等於k的無環路」（這一表述對有權圖和無權圖都有效）。
2、將Hamilton路問題規約到最長無環路問題（的判定版本）是顯然的：輸入一個n頂點的有向圖D，直接問：有向圖D中是否存在長度大於等於n-1的無環路？

簡言之，對任意n頂點的有向圖D，假如能夠D中的找到最長無環路P，那麼就能立即知道D中是否存在Hamilton路（只需看P的長度是否為n-1即可），從而最長無環路問題是NPC。

小規模就直接DFS吧。大規模的時候DFS剪枝。不過確實不好做呀。

有向無圈圖的話可以用dijstra貪心，或者簡單用folyed演算法就可以了（把最小化變為最大化）。

有圈的話您……或者能縮圈么？可以考慮。總之比較復雜。

『柒』 求幫演算法作業！用動態規劃法求解最長路徑問題

先對圖進行拓撲排序 一個結果為s b a c d t 拓撲排序的時候初始化dist[i] 表示從s到i的距離
dist[i]=max{dist[u]+edge[u][i], dist[i]}.
i從s取到t 最終得結果

『捌』 假設2叉樹採用2叉鏈存儲結構 求最長路徑的演算法

strcuct node
{
char* data;
node* left;
node* right;
};

int longestPath(node* root)
{
if (root == NULL)
return 0;
int left_len = 0;
if (root->left != NULL)
left_len = longestPath(root->left) + 1;
int right_len = 0;
if (root->right != NULL)
right_len = longestPath(root->right) + 1;
return left_len > right_len ? letf_len : right_len;
}
沒有明白你要求的最長路徑是什麼最長路徑，二叉樹除了根節點以外都只有一條入度邊，單個節點到單個節點的路徑是唯一的，不存在什麼最長啊。。
不知道你是不是要求二叉樹的高度，給了求二叉樹的高度。