所以另外还需要一个list去储存已经路过的点了，每次找都永远不回头，只要前面出现过就不回去。
不怕这一次找到不一定是最短的，最后综合起来以后肯定是最短的，因为最终是每条路都会走一次。
OK，看算法吧，传进来一个list(储存所有路径信息的) 一个点（自己） 一个目点 计算出下一跳的点（也包括所话费的cost）。
当然这个算法不是最优的，会有重复的计算，会最短路径选择第一次找到那个（应该搞成随机的，这样不会每次去那个点都走这条路，让别的路也来分担一下）
仅供参考，欢迎交流。
JAVA版：
（Vector就是list）
|
public class FindNextRout {
private Vector al;
private String sourcePort;
private String destPort;
private String nextPort;
public FindNextRout(Vector al, String sourcePort, String destPort) {
this.al = al;
this.sourcePort = sourcePort;
this.destPort = destPort;
NextRout();
}
public String getNextPort() {
return nextPort;
}
public void NextRout() {
int a = -1;
String rout = "";
for (Object item : al) {
ArrayList all = new ArrayList();
String[] ss = (item + "").split("\\*");
all.add(ss[0]);
if (sourcePort.equals(ss[0])) {
if (ss[1].equals(destPort)) {
int b = Integer.parseInt(ss[2]);
if (b < a || a == -1) {
a = b;
nextPort = ss[1];
}
} else {
int b = getLeastCost(all, ss[1], destPort);
int c = b + Integer.parseInt(ss[2]);
if (b != -1) {
if (a == -1) {
a = c;
nextPort = ss[1];
} else {
if (c < a) {
a = c;
nextPort = ss[1];
}
}
}
}
}
}
}
public int getLeastCost(ArrayList all, String sourcePort, String destPort) {
int a = -1;
if (!all.contains(sourcePort)) {
all.add(sourcePort);
for (Object item : al) {
String[] ss = (item + "").split("\\*");
if (sourcePort.equals(ss[0])) {
if (!all.contains(ss[1])) {
if (ss[1].equals(destPort)) {
int b = Integer.parseInt(ss[2]);
if (b < a || a == -1) {
a = b;
}
} else {
int b = getLeastCost(all, ss[1], destPort);
int c = b + Integer.parseInt(ss[2]);
if (b != -1) {
if (a == -1) {
a = c;
} else {
if (c < a) {
a = c;
}
}
}
}
}
}
}
}
return a;
}
} |
