程式師世界 >> 編程語言 >> JAVA編程 >> 關於JAVA >> Java生成樹結構各點之間最短路徑算法

Java生成樹結構各點之間最短路徑算法

編輯：關於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 現在來說說如果路徑信息變了要怎麼樣。

路徑信息變了，簡單一句話，把整個路由表刪了，重新計算，這就是所謂的更新路由表。

因為一旦更新路徑，計算機不可能直接就看出來哪更新了，算哪個點就行了，他還是一樣要所有的都看一遍，既然看了，和重新計算已無任何區別，那就直接把所有的刪了就行了。用路由表的時候，要去哪個終點了，算哪個，算完存起來，下次用直接跳存儲的信息就行，不用就不管，扔那，這樣如果一次還沒有全部目的地傳輸一遍的時候，更新路徑信息了，那些沒用過的壓根就沒計算過，也不需要計算，可以節省一部分計算機資源

關於JAVA