Java生成树结构各点之间最短路径算法
先说二叉树,就是一个树形结构,每个点和两个点连接,越往下数量越多,形状看起来就像一棵树一样,故得名二叉树,二叉树用于数据结构可以快速搜索,节约资源提高效率。 每两点之间只有一条路径,无需计算,当然用下述算法一样可以计算的出来。
二叉树图:
再说多叉树,二叉树变种,顾名思义,每个点可以和N个点相连罢了。 同样,每两点之间只有一条路径,无需计算,当然用下述算法一样可以计算的出来,也是在极其蛋疼的情况下。
如图:
生成树 就是多叉树的变种,每一个点都和N个点连接 上下左右都无所谓 乱七八糟一团 最后结果就是随便断一个点 其他各点之间还是有路径可以相连的
如图:
此图属于最小生成树,线程情况可能极其混乱与复杂,放一张我用来测试的图,不完全属于生成树,介于多叉与生成之间。
再说下路由表的概念,现实网络结构就类似于上面这张测试图,要把信息从一台机器上发送到另一台机器上,就要找到一条最短路径(当然现实情况还有许多突发情况需要考虑,这只是最基本的情况)。 其实我觉得吧,干嘛非要自己机器上计算,光存个路由表就得占多大空间去了,就每次需要发送给别人信息的情况下,找自己相邻节点问他们去最终目的地的路径cost,选个最小的发过去完事了,每个人都问下一步要,最后总是能要到最终目的地的,而且本机只需要知道的是下一跳是谁就行,完全不需要保存整个路由信息。
那么,既然非要在本机上计算,那就算给丫看。
思想一样,一步一步问下面要下去。
(代码后面有添加路径信息和删除路由信息时候的计算原则)
首先: 咱得先把所有的路径信息描述出来对吧,总不能扔给计算机一张图让人家自己看去吧(没准以后技术发展发展就真可以了)。
用语句描述起来的话,简单点说,就是一个点*相邻的另一个点*他们之间的cost。
例如此图: 假设每两点间cost是1。
A*B*1
A*C*1
因为是双向连接 所以还需要
B*A*1
C*A*1
所以此算法如果存在单向连接一样可以计算。
把这些连接信息存进一个string数组中。
例如:String[] s = {"A*B*1", "B*A*1", "B*A*1", "C*A*1"}
顺序无所谓,do what ever you want!
第二步,重点来了,就用上面说的那个思想,从头开始一步一步找下去,每一个点都问他直接连接的所有点(当然要除了问他的那个点):你去最终目的地要多少个cost,最后的结果就是从终点那一步,一步一步往前计算下去,最小的留下,其他的扔掉。 典型迭代思想。 一个迭代 全部搞定。
先把string[] 搞成一个list,方便下面使用。
有一点需要注意的是:IMPORTANT!!! 有可能会出现重复。
像下面这个情况:A要去E的最短路径。
A问B要,B问C要,C问D要,D可能又去问B要了。
所以另外还需要一个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;
- }
- }
Python版:(感谢张东方同学帮忙翻译成Python的)
- import os,sys
- from Tool import *
- class FindNextAddress:
- def __init__(self,destAddress,UI):
- try:
- self.nextAddress=UI.routeTable[destAddress]
- #check whether the address is in the routeTable
- #UI.addline('try')
- except:
- #UI.addline('ex1')
- self.UI=UI
- self.sourceAddress=UI.address
- self.destAddress=destAddress
- self.tool=tool()
- #UI.addline(destAddress)
- #UI.addline('ex2')
- self.nextAddress=self.findNextAddress()
- #if the address is not in the routeTable, recalculate the route.
- #UI.addline(self.nextAddress)
- #UI.addline('ex3')
- def getNextAddress(self):
- return self.nextAddress
- #find the next address from the source to the destination
- def findNextAddress(self):
- a=-1
- tempNextAddress=''
- for item in self.UI.routeInfo:
- #self.UI.addline(item+" //// ITEM")
- alreadyPass=[]
- result=item.split('*')
- self.tool.addItemInList(alreadyPass,result[0])
- if self.sourceAddress==result[0]:
- if result[1]==self.destAddress:
- b=int(result[2])
- if b<a or a==-1:
- a=b
- tempNextAddress=result[1]
- else:
- b=self.getLeastCost(alreadyPass,result[1],self.destAddress)
- c=b+int(result[2])
- if b != -1:
- if a==-1:
- a=c
- tempNextAddress=result[1]
- else:
- if c<a:
- a=c
- tempNextAddress=result[1]
- return tempNextAddress
- #get to the most appropriate path
- def getLeastCost(self,alreadyPass,sourceAddress,destAddress):
- a=-159 judge=self.tool.search(alreadyPass,sourceAddress)
- if judge==False:
- self.tool.addItemInList(alreadyPass,sourceAddress)
- for item in self.UI.routeInfo:
- result=item.split('*')
- if sourceAddress==result[0]:
- judgement=self.tool.search(alreadyPass,result[1])
- if judgement==False:
- if result[1]==destAddress:
- b=int(result[2])
- if b<a or a==-1:
- a=b
- else:
- b=self.getLeastCost(alreadyPass,result[1],destAddress)
- c=b+int(result[2])
- if b!=-1:
- if a==-1 or c<a:
- a=c
- return a
OK 现在来说说如果路径信息变了要怎么样。
路径信息变了,简单一句话,把整个路由表删了,重新计算,这就是所谓的更新路由表。
因为一旦更新路径,计算机不可能直接就看出来哪更新了,算哪个点就行了,他还是一样要所有的都看一遍,既然看了,和重新计算已无任何区别,那就直接把所有的删了就行了。 用路由表的时候,要去哪个终点了,算哪个,算完存起来,下次用直接跳存储的信息就行,不用就不管,扔那,这样如果一次还没有全部目的地传输一遍的时候,更新路径信息了,那些没用过的压根就没计算过,也不需要计算,可以节省一部分计算机资源。
原文链接:http://www.cnblogs.com/kevinGuo/archive/2011/12/07/2278702.html
【编辑推荐】
- Java字符编码根本原理
- Java中对象的等价性比较
- Java自定义异常类
- Java编程:数据的截尾与舍入
- Java版A星算法实现步骤