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
【編輯推薦】
