最短路徑演算法java實現

⑴ 求java實現矩陣圖上任意兩點的最短路徑源碼

我用的是遞歸調用方法，有個小問題就是在列印步數的時候是返向的，原因是就是程序不斷的調用自己，到最後判斷基值位準退出調用。這才開始從棧里取出方法進行執行的原因。

代碼欣賞：

publicstaticintstep=1;

=newStringBuffer();

publicstaticint[][]maze={{1,1,1,1,1,1,1,1,1,1,1},

{1,0,1,0,1,0,0,0,0,0,1},

{1,0,1,0,0,0,1,0,1,1,1},

{1,0,0,0,1,0,1,0,0,0,1},

{1,0,1,1,0,0,1,0,0,1,1},//0代表可以通過，1代表不可通過

{1,0,1,0,1,1,0,1,0,0,1},

{1,0,0,0,0,0,0,0,1,0,1},

{1,0,1,0,1,0,1,0,1,0,1},

{1,0,0,1,0,0,1,0,1,0,1},

{1,1,1,1,1,1,1,1,1,1,1}};

publicstaticvoidmain(String[]args){

inti,j;//循環記數變數

Sample.way(1,1);//二維數組起始值從下標1，1開始

System.out.println("起點從坐標x=1,y=1開始");

System.out.println("終點坐標是x=8,y=9結束");

System.out.println("這是迷宮圖表");

System.out.println("012345678910");

System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");

for(i=0;i<10;i++){

System.out.print(""+i+"‖");

for(j=0;j<11;j++)

System.out.print("-"+maze[i][j]+"-‖");

System.out.println("");

System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");

}

//列印顯示步數

System.out.print(printStep.toString());

}

publicstaticbooleanway(intx,inty){

if(maze[8][9]==2)//代表遞歸終止條件（也就是當走出出口時標記為2）

returntrue;

else{

if(maze[y][x]==0){

maze[y][x]=2;

/*

*下面if判斷條件代表當前坐標為基點，

*根據判斷對當前位置進行遞歸調用：如：

*往上、往右上、往右、往右下、往下、

*往左下、往左、往左上的坐標是否可走，

*判斷是否可走的返回條件是：

*2代表可通過、1代表不能通過、3表示已經走過，但是未能走通。

*/

if(way(x,y-1)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x+1,y-1)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x+1,y)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x+1,y+1)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x,y+1)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x-1,y+1)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x-1,y)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}elseif(way(x-1,y-1)){

printStep.append("第"+step+"步的所走的位置是x="+x+"y="+y+" ");

step++;

returntrue;

}else{

maze[y][x]=3;

returnfalse;

}

}else

returnfalse;

}

}

復制代碼前需要樓主自己創建個類

Sample.way(1,1);這句代碼是我的類的靜態調用，改下XXXXX.way(1,1);

XXXXX代表你創建的類。

下面是這個程序運行後的截圖

⑵ 單源最短路徑的Dijkstra演算法

將圖G中所有的頂點V分成兩個頂點集合S和T。以v為源點已經確定了最短路徑的終點並入S集合中，S初始時只含頂點v,T則是尚未確定到源點v最短路徑的頂點集合。然後每次從T集合中選擇S集合點中到T路徑最短的那個點，並加入到集合S中，並把這個點從集合T刪除。直到T集合為空為止。
具體步驟
1、選一頂點v為源點，並視從源點v出發的所有邊為到各頂點的最短路徑（確定數據結構：因為求的是最短路徑，所以①就要用一個記錄從源點v到其它各頂點的路徑長度數組dist[],開始時，dist是源點v到頂點i的直接邊長度，即dist中記錄的是鄰接陣的第v行。②設一個用來記錄從源點到其它頂點的路徑數組path[],path中存放路徑上第i個頂點的前驅頂點）。
2、在上述的最短路徑dist[]中選一條最短的，並將其終點（即<v,k>）k加入到集合s中。
3、調整T中各頂點到源點v的最短路徑。 因為當頂點k加入到集合s中後，源點v到T中剩餘的其它頂點j就又增加了經過頂點k到達j的路徑,這條路徑可能要比源點v到j原來的最短的還要短。調整方法是比較dist[k]+g[k,j]與dist[j]，取其中的較小者。
4、再選出一個到源點v路徑長度最小的頂點k,從T中刪去後加入S中，再回去到第三步，如此重復，直到集合S中的包含圖G的所有頂點。 SPFA實際上是Bellman-Ford基礎上的隊列優化
SPFA(G,w,s)
1. INITIALIZE-SINGLE-SOURCE(G,s)
2. INITIALIZE-QUEUE(Q)
3. ENQUEUE(Q,s)
4. While Not EMPTY(Q)
5. Do u<-DLQUEUE(Q)
6. For 每條邊(u,v) in E[G]
7. Do tmp<-d[v]
8. Relax(u,v,w)
9. If (d[v] < tmp) and (v不在Q中)
10. ENQUEUE(Q,v)
c++：
boolSPFA(intsource)
{
deque<int>dq;
inti,j,x,to;
for(i=1;i<=nodesum;i++)
{
in_sum[i]=0;
in_queue[i]=false;
dist[i]=INF;
path[i]=-1;
}
dq.push_back(source);
in_sum[source]++;
dist[source]=0;
in_queue[source]=true;
//初始化完成
while(!dq.empty())
{
x=dq.front();
dq.pop_front();
in_queue[x]=false;
for(i=0;i<adjmap[x].size();i++)
{
to=adjmap[x][i].to;
if((dist[x]<INF)&&(dist[to]>dist[x]+adjmap[x][i].weight))
{
dist[to]=dist[x]+adjmap[x][i].weight;
path[to]=x;
if(!in_queue[to])
{
in_queue[to]=true;
in_sum[to]++;
if(in_sum[to]==nodesum)
return false;
if(!dq.empty())
{
if(dist[to]>dist[dq.front()])
dq.push_back(to);
else
dq.push_front(to);
}
else
dq.push_back(to);
}
}
}
}
returntrue;
}

⑶ 用Java實現一個地鐵票價計算程序，希望給出主要演算法與數據結構

根據某市地鐵線路圖寫一個地鐵票價計算程序

需求描述：

1.計費規則：最低2元，超過5站以上每站加收0.5元，換乘重新起算，例如L1先坐4站，換乘L2再坐6站，結果就是2+2.5=5.5元

2.程序啟動以後讀取輸入文件（in.txt），內容格式如：

L2-8,L2-2

X3,L3-8

....

每行表示一次行程，起點站和終點站之間用逗號分隔，行數不限

4.系統按最短路徑方案（盡量少換乘且站數少，假設乘 客換乘一次用的時間相當於坐4個站）規劃路線，計算票價，並把路線和票價輸出到文件(out.txt)，內容格式如：

L2-8,L2-2=2.5:L2-8,L2-7,L2-6,L2-5,L2-4,L2-3,L2-2

X3,L3-8=4:X3,X4,L3-8

....

等號後面的表示票價和路徑

地鐵線路圖如下：共有5條線路，X開頭的站點表示 換乘車站

⑷ 求java演算法源代碼 求出汽車從起點S出發到達終點T的一條行駛路程最短的路線。

呵呵，你如果最短路徑是m*n的這個前提就好算；如果最短不一定是m*n的話就成了一個迷宮問題同樣求指點啊