最长路径算法

‘壹’ 图中的最长路径问题怎么算

把距离取负值就是个最短路径问题，有负权值的最短路径不适用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;
}
没有明白你要求的最长路径是什么最长路径，二叉树除了根节点以外都只有一条入度边，单个节点到单个节点的路径是唯一的，不存在什么最长啊。。
不知道你是不是要求二叉树的高度，给了求二叉树的高度。