點(diǎn)對(duì)點(diǎn)Dijkstra算法的改進(jìn)用于求兩點(diǎn)間的所

1、點(diǎn)對(duì)點(diǎn)Dijkstra算法的改進(jìn)用于求兩點(diǎn)間的所有最短路徑importjava.util.Vector;importjava.util.StringTokenizer;*這是一個(gè)點(diǎn)對(duì)點(diǎn)（S-T）Dijkstra算法的改進(jìn)。用于求兩點(diǎn)間的所有最短路徑。*authorFe*/publicclassSTDijkstraAdv*所求路經(jīng)所在圖的鄰接鏈表引用* /GraphAdjListgraphAdjList口=null;/* 圖中總的結(jié)點(diǎn)數(shù)。* /inttotalNodeNum;/* 源結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)。* /intsourceNode,targetNode;/* 兩結(jié)點(diǎn)間的路徑長(zhǎng)度。* /intdi

2、stance=-1;/* 前驅(qū)結(jié)點(diǎn)鏈表數(shù)組。* /PreNodespreNodes=null;/* 用一個(gè)圖的鄰接表引用構(gòu)造一個(gè)實(shí)例引用。* paramgraph* 圖的鄰接表引用* /publicSTDijkstraAdv(GraphAdjListgraph)graphAdjList=graph;totalNodeNum=graphAdjList.length;preNodes=newPreNodestotalNodeNum;)/* 用一個(gè)圖的鄰接表以及源結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)構(gòu)造一個(gè)實(shí)例引用。* paramgraph* 圖的鄰接表引用* paramsource源結(jié)點(diǎn)paramtarget目標(biāo)結(jié)點(diǎn)*

3、/publicSTDijkstraAdv(GraphAdjListgraph,intsource,inttarget)graphAdjList=graph;totalNodeNum=graphAdjList.length;preNodes=newPreNodestotalNodeNum;setST(source,target);)/* 設(shè)置源結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)。用于求不同的結(jié)點(diǎn)間的最短路徑。* params* 源結(jié)點(diǎn)* paramt* 目標(biāo)結(jié)點(diǎn)* /publicvoidsetST(ints,intt)sourceNode=s;targetNode=t;for(inti=0;i<tot

4、alNodeNum;i+)preNodesi=newPreNodes();preNodesi.preNode=sourceNode;)/* 返回所求最短路徑的路徑長(zhǎng)度。* return* 所求路徑的總路徑長(zhǎng)度* /publicintgetDistance()returndistance;)* 返回從結(jié)點(diǎn)s到結(jié)點(diǎn)t得最短路徑長(zhǎng)度* params* 源結(jié)點(diǎn)* paramt* 目標(biāo)結(jié)點(diǎn)* return* 所求得的最短路徑長(zhǎng)度* /publicintgetDistance(ints,intt)setST(s,t);go();returndistance;)* 返回所求結(jié)點(diǎn)間最短路徑子圖。* 用二維數(shù)組

5、表示。* 每一行表示一條最短路徑。* return*所求結(jié)點(diǎn)間最短路徑構(gòu)成的最短路徑子圖。*/publicint口getPath()/用深度優(yōu)先法從前驅(qū)表中求出每條最短路徑。PreNodestemp=preNodestargetNode;Vectorstack=newVector();booleanfirstTime=true;/用于存儲(chǔ)每次求得的一條最短路徑。Vectorv=newVector();v.add(newInteger(targetNode);/以0d1dt2d3d4dt的形式存儲(chǔ)所有最短路徑。/d表示每條最短路徑內(nèi)每個(gè)節(jié)點(diǎn)的分隔符，t表示各條最短路徑的分隔符StringallP

6、athTemp=newString("");intpathNum=0;while(!stack.isEmpty()|firstTime)if(!firstTime)/branchNode用于表示上一次路徑分支點(diǎn)的那個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)號(hào)。IntegerbranchNode=(Integer)(stack.remove(stack.size()-1);分支節(jié)點(diǎn)的節(jié)點(diǎn)前驅(qū)信息。temp=(PreNodes)stack.remove(stack.size()-1);在上一條最短路徑中，將在分支點(diǎn)以后的節(jié)點(diǎn)號(hào)刪除。inti=v.indexOf(branchNode);for

7、(intj=v.size();i<j;j-)v.remove(j-1);找一條最短路徑。while(Integer)v.get(v.size()-1).intValue()!=sourceNode)v.add(newInteger(temp.preNode);if(temp.anotherPreNode!=null)stack.add(temp.anotherPreNode);stack.add(newInteger(temp.preNode);temp=preNodestemp.preNode;將求得的最短路徑按0d1dt2d3d4dt的形式存放在allPathTemp中。/當(dāng)

8、求得所有最短路徑后再解析。for(inti=0;i<v.size();i+)allPathTemp+=(Integer)(v.get(i).toString()+"d");allPathTemp+="t"pathNum+;firstTime=false;存放所有最短路徑的數(shù)組。intpath=newintpathNum口；/以2d3d4dt的形式存放一條最短路徑的數(shù)組。等待進(jìn)一步解析。StringpathTemp=newStringpathNum;第一步解析，根據(jù)t將各條最短路徑分開。pathTemp=fil

9、terAllPathTemp(allPathTemp,pathNum);for(inti=0;i<pathNum;i+)第二步解析，根據(jù)d將每條最短路徑內(nèi)的各個(gè)結(jié)點(diǎn)分開。pathi=filterPathTemp(pathTempi);)returnpath;)第一步解析，根據(jù)t將各條最短路徑分開。privateStringfilterAllPathTemp(Stringpath,intnum)StringTokenizerst=newStringTokenizer(path,"t");StringpathTemp=newStringnum;fo

10、r(inti=0;i<num;i+)pathTempi=st.nextToken();)returnpathTemp;)第二步解析，根據(jù)d將每條最短路徑內(nèi)的各個(gè)結(jié)點(diǎn)分開。privateintfilterPathTemp(StringpathTemp)StringTokenizerst=newStringTokenizer(pathTemp,"d");intnodeNum=0;/求得這條最短路徑包含的結(jié)點(diǎn)數(shù)。trywhile(true)st.nextToken();nodeNum+;)catch(Exceptione)st=newStringTo

11、kenizer(pathTemp,"d");intpath=newintnodeNum;for(inti=0;i<nodeNum;i+)pathi=Integer.parseInt(st.nextToken();returnpath;publicvoidgo(ints,intt)setST(s,t);go();)暫不考慮非連同情形，待改進(jìn)。publicvoidgo()/用于存儲(chǔ)從源結(jié)點(diǎn)到其他各個(gè)結(jié)點(diǎn)的最短路徑長(zhǎng)度的tempointdistanceTemp口=newinttotalNodeNum;/初始時(shí)將從源結(jié)點(diǎn)到其他各個(gè)結(jié)點(diǎn)的最短路徑長(zhǎng)度全都

12、設(shè)置為無(wú)窮遠(yuǎn)。除源結(jié)點(diǎn)到自身的長(zhǎng)度為00for(inti=0;i<totalNodeNum;i+)distanceTempi=0X0FFFFFFF;)distanceTempsourceNode=0;根據(jù)圖的鄰接表具有的信息，將于源結(jié)點(diǎn)鄰接的結(jié)點(diǎn)的路徑長(zhǎng)度設(shè)置為邊的權(quán)值，其余不變,作為長(zhǎng)度初始值。NextAdjNodetemp=null;temp=graphAdjListsourceNode.firstNode;distanceTemptemp.nodeNum=temp.edgeWeight;while(temp.nextNode!=null)temp=temp.nextNode

13、;distanceTemptemp.nodeNum=temp.edgeWeight;)intnextNodes口=newint1;nextNodes0=sourceNode;/如果目的節(jié)點(diǎn)沒(méi)有包含在找到的節(jié)點(diǎn)當(dāng)中，則繼續(xù)找。while(!containTargetNode(nextNodes)nextNodes=chooseNextPathNode(distanceTemp,distanceTempnextNodes0);updateDistance(nextNodes,distanceTemp);)distance=distanceTemptargetNode;)privateboolean

14、containTargetNode(intnextNodes)if(nextNodes=null)returnfalse;)for(inti=0;i<nextNodes.length;i+)if(nextNodesi=targetNode)returntrue;)returnfalse;)privateintchooseNextPathNode(intdistanceTemp,intcurrentPathLength)inttemp=0X0FFFFFFF;VectornextNodeTemp=newVector();從源結(jié)點(diǎn)到每個(gè)其余節(jié)點(diǎn)的距離進(jìn)行比較，在這個(gè)距離大于上一次的最小

15、距離的前提下，如果源結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)距離是最小的，則修改最小距離，并將著這節(jié)點(diǎn)設(shè)為下一個(gè)找到的結(jié)點(diǎn)；如果源結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)的距離與目前找到得最短距離相等，則追加到下一次找到的結(jié)點(diǎn)數(shù)組中。for(inti=0;i<totalNodeNum;i+)if(temp>distanceTempi)&&(distanceTempi>currentPathLength)&&(i!=sourceNode)temp=distanceTempi;nextNodeTemp.clear();nextNodeTemp.

16、add(newInteger(i);elseif(temp=distanceTempi)nextNodeTemp.add(newInteger(i);intnextNodes=newintnextNodeTemp.size();for(inti=0;i<nextNodeTemp.size();i+)nextNodesi=(Integer)nextNodeTemp.get(i).intValue();returnnextNodes;privatevoidupdateDistance(intcurrentNodes,intdistanceTemp)/根據(jù)本次找到的結(jié)點(diǎn)數(shù)組，對(duì)源結(jié)點(diǎn)到

17、各點(diǎn)的距離進(jìn)行更新。/如果距離變小了，就修改這個(gè)距離和這個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。如果距離與原來(lái)的距離相等，則將本次找到的節(jié)點(diǎn)數(shù)組中的某個(gè)結(jié)點(diǎn)追加到這個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)鏈表中。for(inti=0;i<currentNodes.length;i+)NextAdjNodetemp=null;if(graphAdjListcurrentNodesi!=null)temp=graphAdjListcurrentNodesi.firstNode;while(temp!=null)if(distanceTempcurrentNodesitemp.edgeWeightdistanceTemptemp.nodeNum)distanceTemptemp.nodeNumtemp.edgeWeight;distanceTempcurrentNodesi<+preNodestemp.nodeNum.anotherPreNode=null;preNodestemp.nodeNum.preNode=currentNodesi;elseif(distanceTempcurrentNodesi+temp.edgeWeightdistanceTemptemp.nodeNum)append(preNodestemp.nodeNum,currentNod