⑴ 求帮算法作业！用动态规划法求解最长路径问题
先对图进行拓扑排序 一个结果为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，因为两点之间最多只有一条路相通