请问怎么寻找有向无环图(DAG）的最长路径以及两个顶点之间的路径总数

请教如何寻找有向无环图(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))

Java code

public static int longestPath(int node,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);    }

只写了这样的code，但是不能算出最长的路径……topo是排序好的拓扑顺序
时间比较急，所以只好上来问了，哪怕只是给一个能够运作的伪代码也行，谢谢大家了！

[解决办法]
enum VertexState{White, Gray, Black}

public void DFS(){
for (int i = 0; i < order(); i++){
state[i] = VertexState.White;
}
int time = 0;
for(int u = 0;u<order();u++){
time = recursiveDFS(u,time);
}

int[] topo = topoSort(doneTimes);
System.out.println(longestPath(0,topo));
}
public int recursiveDFS(int u,int time){
if(state[u] != VertexState.White){
return time;
}
state[u] = VertexState.Gray;
//System.out.format("%d is seen, time is %d\n",u,time);
seenTimes[u] = time;
time++;
int lastTime = time;
for(int v = 0; v < order(); v++){
if(isArc(u, v) && state[v] == VertexState.White){
pred[v] = u;
time = recursiveDFS(v,time);
}
}
if(lastTime == time){
leavesSeenTimes.add(time-1);
}
//System.out.format("%d is done, time is %d\n",u,time);
state[u] = VertexState.Black;
doneTimes[u] = time;
time++;
return time;
}

查看更多 下一篇