我想知道如何从节点 0(最小节点)开始获得 DAG 中的最长路径
我搜索了wiki并得到了以下算法:
algorithm dag-longest-path is
input:
Directed acyclic graph G
output:
Length of the longest path
length_to = array with |V(G)| elements of type int with default value 0
for each vertex v in topOrder(G) do
for each edge (v, w) in E(G) do
if length_to[w] <= length_to[v] + weight(G,(v,w)) then
length_to[w] = length_to[v] + weight(G, (v,w))
return max(length_to[v] for v in V(G))
但是我不知道怎么实现,当然下面我写的代码是行不通的:(topo是拓扑排序的节点)
public static int longestPath(int[] topo){
int[] dist = new int[topo.length];
for(int i:topo){
if(isArc(node,i)){
if(dist[i]<dist[node]+1){
dist[i] = dist[node] + 1;
}
}
}
return getMax(dist);
}
我应该怎么做?谢谢!
此外,你能给我一个算法来计算从 0 到 n-1 的不同路径的数量吗?