Java生成樹結(jié)構(gòu)各點(diǎn)之間最短路徑算法
先說二叉樹，就是一個(gè)樹形結(jié)構(gòu)，每個(gè)點(diǎn)和兩個(gè)點(diǎn)連接，越往下數(shù)量越多，形狀看起來就像一棵樹一樣，故得名二叉樹，二叉樹用于數(shù)據(jù)結(jié)構(gòu)可以快速搜索，節(jié)約資源提高效率。 每?jī)牲c(diǎn)之間只有一條路徑，無需計(jì)算，當(dāng)然用下述算法一樣可以計(jì)算的出來。
二叉樹圖：
再說多叉樹，二叉樹變種，顧名思義，每個(gè)點(diǎn)可以和N個(gè)點(diǎn)相連罷了。 同樣，每?jī)牲c(diǎn)之間只有一條路徑，無需計(jì)算，當(dāng)然用下述算法一樣可以計(jì)算的出來，也是在極其蛋疼的情況下。
如圖：
生成樹 就是多叉樹的變種，每一個(gè)點(diǎn)都和N個(gè)點(diǎn)連接 上下左右都無所謂 亂七八糟一團(tuán) 最后結(jié)果就是隨便斷一個(gè)點(diǎn) 其他各點(diǎn)之間還是有路徑可以相連的
如圖：
此圖屬于最小生成樹，線程情況可能極其混亂與復(fù)雜，放一張我用來測(cè)試的圖，不完全屬于生成樹，介于多叉與生成之間。
再說下路由表的概念，現(xiàn)實(shí)網(wǎng)絡(luò)結(jié)構(gòu)就類似于上面這張測(cè)試圖，要把信息從一臺(tái)機(jī)器上發(fā)送到另一臺(tái)機(jī)器上，就要找到一條最短路徑（當(dāng)然現(xiàn)實(shí)情況還有許多突發(fā)情況需要考慮，這只是最基本的情況）。 其實(shí)我覺得吧，干嘛非要自己機(jī)器上計(jì)算，光存?zhèn)€路由表就得占多大空間去了，就每次需要發(fā)送給別人信息的情況下，找自己相鄰節(jié)點(diǎn)問他們?nèi)プ罱K目的地的路徑cost，選個(gè)最小的發(fā)過去完事了，每個(gè)人都問下一步要，最后總是能要到最終目的地的，而且本機(jī)只需要知道的是下一跳是誰就行，完全不需要保存整個(gè)路由信息。
那么，既然非要在本機(jī)上計(jì)算，那就算給丫看。
思想一樣，一步一步問下面要下去。
（代碼后面有添加路徑信息和刪除路由信息時(shí)候的計(jì)算原則）
首先： 咱得先把所有的路徑信息描述出來對(duì)吧，總不能扔給計(jì)算機(jī)一張圖讓人家自己看去吧（沒準(zhǔn)以后技術(shù)發(fā)展發(fā)展就真可以了）。
用語句描述起來的話，簡(jiǎn)單點(diǎn)說，就是一個(gè)點(diǎn)*相鄰的另一個(gè)點(diǎn)*他們之間的cost。
例如此圖： 假設(shè)每?jī)牲c(diǎn)間cost是1。
A*B*1
A*C*1
因?yàn)槭请p向連接 所以還需要
B*A*1
C*A*1
所以此算法如果存在單向連接一樣可以計(jì)算。
把這些連接信息存進(jìn)一個(gè)string數(shù)組中。
例如：String[] s = {"A*B*1", "B*A*1", "B*A*1", "C*A*1"}
順序無所謂，do what ever you want!
第二步，重點(diǎn)來了，就用上面說的那個(gè)思想，從頭開始一步一步找下去，每一個(gè)點(diǎn)都問他直接連接的所有點(diǎn)（當(dāng)然要除了問他的那個(gè)點(diǎn)）：你去最終目的地要多少個(gè)cost，最后的結(jié)果就是從終點(diǎn)那一步，一步一步往前計(jì)算下去，最小的留下，其他的扔掉。 典型迭代思想。 一個(gè)迭代 全部搞定。
先把string[] 搞成一個(gè)list,方便下面使用。
有一點(diǎn)需要注意的是：IMPORTANT!!! 有可能會(huì)出現(xiàn)重復(fù)。
像下面這個(gè)情況：A要去E的最短路徑。
A問B要，B問C要,C問D要，D可能又去問B要了。
所以另外還需要一個(gè)list去儲(chǔ)存已經(jīng)路過的點(diǎn)了，每次找都永遠(yuǎn)不回頭，只要前面出現(xiàn)過就不回去。
不怕這一次找到不一定是最短的，最后綜合起來以后肯定是最短的，因?yàn)樽罱K是每條路都會(huì)走一次。
OK，看算法吧，傳進(jìn)來一個(gè)list(儲(chǔ)存所有路徑信息的) 一個(gè)點(diǎn)（自己） 一個(gè)目點(diǎn) 計(jì)算出下一跳的點(diǎn)（也包括所話費(fèi)的cost）。
當(dāng)然這個(gè)算法不是最優(yōu)的，會(huì)有重復(fù)的計(jì)算，會(huì)最短路徑選擇第一次找到那個(gè)（應(yīng)該搞成隨機(jī)的，這樣不會(huì)每次去那個(gè)點(diǎn)都走這條路，讓別的路也來分擔(dān)一下）
僅供參考，歡迎交流。
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版：（感謝張東方同學(xué)幫忙翻譯成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 現(xiàn)在來說說如果路徑信息變了要怎么樣。
路徑信息變了，簡(jiǎn)單一句話，把整個(gè)路由表刪了，重新計(jì)算，這就是所謂的更新路由表。
因?yàn)橐坏└侣窂剑?jì)算機(jī)不可能直接就看出來哪更新了，算哪個(gè)點(diǎn)就行了，他還是一樣要所有的都看一遍，既然看了，和重新計(jì)算已無任何區(qū)別，那就直接把所有的刪了就行了。 用路由表的時(shí)候，要去哪個(gè)終點(diǎn)了，算哪個(gè)，算完存起來，下次用直接跳存儲(chǔ)的信息就行，不用就不管，扔那，這樣如果一次還沒有全部目的地傳輸一遍的時(shí)候，更新路徑信息了，那些沒用過的壓根就沒計(jì)算過，也不需要計(jì)算，可以節(jié)省一部分計(jì)算機(jī)資源。
原文鏈接：http://www.cnblogs.com/kevinGuo/archive/2011/12/07/2278702.html
【編輯推薦】
