⑴ 求幫演算法作業！用動態規劃法求解最長路徑問題
先對圖進行拓撲排序 一個結果為s b a c d t 拓撲排序的時候初始化dist[i] 表示從s到i的距離
dist[i]=max{dist[u]+edge[u][i], dist[i]}.
i從s取到t 最終得結果
⑵ 靜態鏈表建立一棵樹,並求根結點到葉子的最長路徑的演算法
int maxdeep(int x)
{
if(x have no child)
return 1;
int deep=0;
for(x's every child)
{
deep=max(deep,maxdeep(x'child)+1)
}
return deep;
}
⑶ 輸出二叉樹最長路徑 演算法中 恢復環境不懂
你好，我看了這個程序。你的理解是正確的。這個恢復現場對程序的計算並沒有影響。可以不要的。
另外，拿不準的時候，建議直接實驗測試，注釋掉最後一行，看運行結果是不是正確的。如果正確就說明沒問題。
⑷ 圖中的最長路徑問題怎麼算
把距離取負值就是個最短路徑問題，有負權值的最短路徑不適用dijkstra演算法，但基於鬆弛技術的bellmanford和floyd演算法都是適用的，計算多點之間最短路徑使用floyd演算法
具體來說是進行n-2輪鬆弛，即對任意兩點窮舉第三點，並嘗試將距離替換成經由第三點的距離。完成後額外進行一輪鬆弛，如果距離繼續變小，說明存在負權有向環，最短路徑不存在（可以不斷沿著環繞），否則當前路徑就是最短路徑。
⑸ 請教無向無環圖最長路徑演算法
無向無環圖就是樹，
從根出發：
如果是計算最多的路徑，就用廣度優先（層次遍歷）就可以了，最後訪問的頂點一定是最多的路徑的
如果是計算最長的路徑長度，直接將上面的演算法改一下，每個頂點時記下前面的來路的值加上現在的，就可以求出最大值
或者直接用Dijkstra
演算法就可以了
⑹ spfa 怎麼解決 最長路的問題 （為無向圖且保證出現正環）
SPFA可以處理負環，記錄一個點出現的次數，只要這個點出現次數超過n次（n為總點數），就證明有負環
事實上，把正邊權改為負邊權是可以的，也很方便；但是有時SPFA可以直接修改演算法中的大於號或小於號，這不適用於Dijkstra
邊權取負是最常用的，題目一般會保證沒有負環，如果有的話一般會讓輸出impossible這樣的字串
下面是我SPFA的一個板子
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
int to,next,len;
}edge[(int)1e5+5];
struct Node
{
int head,dis;
bool vis;
}node[(int)1e5+5];
int cnt;
int addEdge(int u,int v,int w)
{
edge[++cnt].len=w;
edge[cnt].to=v;
edge[cnt].next=node[u].head;
node[u].head=cnt;
}
int u,v,w;
int n,m;
int SPFA()
{
queue<int>q;
for(int i=1;i<=n;i++)
{
node[i].dis=INF;
node[i].vis=false;
}
node[1].dis=0;
node[1].vis=true;
q.push(1);
while(not q.empty())
{
int u=q.front();
q.pop();
node[u].vis=false;
for(int e=node[u].head;e;e=edge[e].next)
{
int v;
if(node[v=edge[e].to].dis<=node[u].dis+edge[e].len)continue;
node[v].dis=node[u].dis+edge[e].len;
/*只要在這里加一個判斷，
c[v]++;//更新出現次數
if(c[v]>n) return 0;*/
if(!node[v].vis)
{
q.push(v);
node[v].vis=true;
}
}
}
if(node[n].dis==INF)
{
puts("impossible");
exit(0);
}
return node[n].dis;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
addEdge(u,v,w);//根據題目要求是否取相反數
}
cout<<SPFA()<<endl;
return 0;
}
純手打，很累，不理解繼續問，求採納
⑺ 可以用求最短路徑的方法思想求最長路徑么為什麼
floyed演算法可以有迴路，但是不能有負權迴路。
最長路問題分成兩種：
1. 可以走重復邊。
2. 不能走重復邊。
如果是1的話，那麼如果圖中有一條權為正的環，那麼你沿著環反復走就得到無限長的路了，而如果沒有這樣的環的話，Bellman–Ford（單源）或者Floyed（任意點對）演算法都可以計算出正確的解。
⑻ 數據結構AOE網最長路徑問題
圖中每個頂點表示事件，每條弧表示活動，從定義中也可以知道，最長路徑即是關鍵路徑，此圖可以表示一個工程的流程圖，一個工程的最早完成時間自然是工程中所有最花費時間的活動都已完成所花費的最長時間，因為工程中的某些子工程是可以同時進行的。大概就是這樣，如果要問這個18是怎麼求出來的，這個問題就難以解釋了，因為本身演算法就很復雜，不是幾句話就能說清楚的。上面這個圖是清華大學計算機系教授嚴蔚敏與吳偉民所合編的《數據結構（C語言版）》中的原圖，建議你搜索嚴蔚敏的視頻看一看，共48集，多看幾遍應該就沒什麼問題了
⑼ Floyd演算法可以用來求最長路徑嗎請給出原理證明！如若不能，請給出理由！謝謝！！！
有環圖不存在最長路徑吧？因為可以無限繞圈
如果是無環圖的話，把所有邊取相反數，就變成了求最短路，可以使用floyd，因為兩點之間最多隻有一條路相通