最长路径如何获取

Question

如：有以下流程
0
1      
2（1-2用时10秒 2为分支节点）      
3（2-3用时20秒）   5（2-5用时20秒）
4（3-4用时30秒）   7（5-7用时50秒）
6 （4-6用时40秒 7-6用时70秒 6为汇聚节点）如何计算最长路径用时如以上流程最长用时为 0-1-2-5-7-6；请大家提供代码，500分相送！

Answer 1

这是求最短的,你看看对你是否有用
http://blog.sina.com.cn/s/blog_5fc3da040100dec7.html

Answer 2

最短和最长好像差别比较大，主要是俺java不熟！郁闷，丁丁！

Answer 3

没有时间细想，只给点看法，用决策树来解决，楼主认为然否？可以Google一下。因为你的叙述中，每步都是取最大价值的解。

Answer 4

答：本质上与关键路径算法相似。
参考代码：package longestpath;//求最长路径
public class Path { private static int[][]  graph={
//0--表示不存在有向边
{0,5,0,0,0,0,0,0}, //0
{0,0,10,0,0,0,0,0}, //1
{0,0,0,20,0,20,0,0}, //2
{0,0,0,0,30,0,0,0}, //3
{0,0,0,0,0,0,40,0}, //4
{0,0,0,0,0,0,0,50}, //5
{0,0,0,0,0,0,0,0}, //6
{0,0,0,0,0,0,70,0} //7
};
private static String[] path=new String[graph.length];//每一个结点的目前的路径
private static int[] value=new int[graph.length];//结点目前的路径值

private static int[] indegree=new int[graph.length];//每一个结点的入度
private static int[] stack=new int[graph.length+1];//入度为零的结点栈
private static int top=-1;//栈指针。-1表示空栈
private static int total=0;//已计算了多少个结点

private static void init()//初始化
{
for(int i=0;i<graph.length;i++)
{
path[i]="";
value[i]=0;

}
}

//从0t结点开始计算
private static void calPath()
{
path[0]="0";
value[0]=0;
//计算每一个结点的入度，若为零，则进栈
for(int i=0;i<graph.length;i++)
{
for(int j=0;j<graph.length;j++)
{
if(graph[j][i]!=0){indegree[i]++;}
}
if(indegree[i]==0) stack[++top]=i;//入栈
}//for
while(top>=0)//栈不空时
{
int p=stack[top--];//出栈
for(int j=0;j<graph.length;j++)//对每一个p发出的有向边:p->j
{
if(graph[p][j]!=0)//p->j是一条有向边
{
if(value[p]+graph[p][j]>value[j])
{//比它现有的值更大
value[j]=value[p]+graph[p][j];//记下新值
path[j]=path[p]+"->"+j;//记下路径
}
//p->j已计算过，j的入度减1（相当于去掉p->j这条有向边）,若为零，则入栈
if(--indegree[j]==0){stack[++top]=j;}
}//if
}
total++;//已计算了一个结点。
}//while
if(total<graph.length)
{
System.out.println("有向图中有环路，无法计算。");
System.exit(-1);
}

}//calPath

//打印路径与值
//end--汇集结点
private static void print(int end)
{
System.out.println("最长路径："+path[end]+"  值："+value[end]);
}

public static void main(String[] args) {
// TODO 自动生成方法存根
       calPath();//求最长路径
       print(6);//打印汇集结点6的路径与值
}}
程序运行结果：
最长路径：0->1->2->5->7->6  值：155