日期:2014-05-20  浏览次数:20697 次

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