求一个最优路径算法的思路

Question

求一个最优路径算法的思路，在最近项目开发的过程中，需要用到下面这样一个算法：用户可以输入比如1-2 2-3 2-1 3-4 4-5 6-1之类的数字对，要求能求出它的最优路径-----（指的是最长的那一条，比如上面的路径有2-3-4-5，也有6-1-2，还有1-2-3-4-5等等之类的，越长越优，但是不能出现封闭的路径，比如1-2-1这种,还有就是如果说你有两条或更多不同的最长路径都可以是最优路径，那任选其一就可以了）
求高手用java代码写出来（下面是我写好的用户输入部分，可以得到用户输入的每个键值对，用二维数组保存起来了，只需要出求最优路径算法的函数就可以了，写出来了我再给100分）：

public class SuanFa
{
public static void main(String [] args) throws Exception
{
System.out.println("你输入的参数对为:");
if(args.length>0)
{

String [][] strArray =new String[args.length][2];
for(int i=0;i<args.length;i++)
{
/*取出用户输入的键值对并加入到二维数组strArray中*/
String argValue=args[i];
String [] keyAndValue=argValue.split("-", 2);
String key= keyAndValue[0];
String value= keyAndValue[1];
strArray[i][0]=key;
strArray[i][1]=value;
}

for(int i=0;i<strArray.length;i++)
{
System.out.print(strArray[i][0]+"-"+strArray[i][1]);
System.out.println();
}

}
else
{
System.out.println("请输入参数!");
}

}
我上面的路径只是举几个例子，没有全部写出来，但是意思就是要找最长的那一条！

Answer 1

同意楼上，最长路径是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算法就可以了（把最小化变为最大化）。

有圈的话您……或者能缩圈么？可以考虑。总之比较复杂。

Answer 2

不太明白你的题意！
1-2 2-3 2-1 3-4 4-5 6-1中包含2-3-4-5、6-1-2、1-2-3-4-5！这是什么意思？是否包含6-1-2-3-4-5

Answer 3

挺简单的，不需要多少代码。

public class Test{
private ArrayList<int[]> Longest = new ArrayList<int[]>();

public static void main(String[] argStrings) throws Exception {
Test test = new Test();
ArrayList<int[]> list = test.ceshiShuju();
for (int i = 0; i < list.size(); i++) {
test.run(i, new ArrayList<int[]>(list), new ArrayList<int[]>());
}
System.out.println("最长路径：");
for (int[] pair : test.Longest){
System.out.print(pair[0] + "-" + pair[1] + "\t");
}
}

//产生随机的测试数据
private ArrayList<int[]> ceshiShuju(){
ArrayList<int[]> list = new ArrayList<int[]>();
for (int i = 0; i < 12; i++){
int a = (int)(Math.random() * 10);
int b;
while ((b = (int)(Math.random() * 10)) == a) {
}
list.add(new int[]{a, b});
}

System.out.println("随机产生的测试数据：");
for (int[] pair : list){
System.out.print(pair[0] + "-" + pair[1] + "\t");
}
System.out.println();
return list;
}

//寻找最长路径
private void run(int index, ArrayList<int[]> pairList, ArrayList<int[]> path){
int[] pair = pairList.remove(index);
for (int[] a : path) {
if (a[0] == pair[1]) {
return;
}
}
path.add(pair);
if (path.size() > this.Longest.size()) {
this.Longest = path;
}
for (int i = 0; i < pairList.size(); i++) {
if(pair[1] == pairList.get(i)[0]){
this.run(i, new ArrayList<int[]>(pairList), new ArrayList<int[]>(path));
}
}
}
}

Answer 4

我记得最长路是一个NPC问题，如果让我去做的话，DFS+剪枝吧～
或者把每条边的权值取反，求一次最短路（Spfa）～