Dijkstra算法是按照路徑長度遞增的方法計算某一點到其余各頂點的最短路徑。其算法的基本思想是：把圖中所有頂點分成兩組，第一組包括已確定最短路徑的頂點(初始只包括源點v0)，第二組包括尚未確定最短路徑的頂點，然后按最段路徑長度遞增的次序逐個把第二組的頂點加到第一組中去，直至從v0可以到大的所有頂點都包括到第一組中。在這個過程中，總保持v0到第一組各頂點的最短路徑都不大于從v0到第二組的任何頂點的最短路徑長度。另外，每一頂點都對應一個距離值，第一組的頂點對應的距離值就是從v0到此頂點的只包括第一組的頂點為中間頂點的最短距離。

這里使用以下圖進行說明:

該圖的鄰接矩陣如下所示:

代碼:package?單源頂點最短路徑Dijkstra;

/**

*?@author?wangyq

*?@Date?2016-09-04?15:57

*/

/*

*?單源頂點最短路徑問題求解:

*?最短路徑問題:給定帶權有向圖G和源點v0，求從v0到圖中其他各頂點的最短距離.

*?Dijkstra算法：按路徑長度遞增的方法計算某一點到其余各點的最短距離。

*/

public?class?Dijkstra?{

/*

*?max:給出的極大值，表示頂點之間無法到達

*?dist[]:存儲最短路徑長度的數組

*?prve[]:存儲當前頂點的前驅頂點

*?a[][]:給定測試的鄰接矩陣表

*/

private?static?int?max=Integer.MAX_VALUE;

private?static?int?dist[]=new?int[6];

private?static?int?prve[]=new?int[6];

private?static?int?a[][]={

{0,max,10,max,30,100},

{max,0,5,max,max,max},

{max,max,0,50,max,max},

{max,max,max,0,max,10},

{max,max,max,20,0,60},

{max,max,max,max,max,0}

};

//dijkstra算法

public?void?dijkstra(int?v,int?[][]a,int?dist[],int?prve[]){

int?n=dist.length-1;

//s[]:存儲已經找到最短路徑的頂點，false為未求得

boolean[]s=new?boolean[n+1];

for(int?i=1;i<=n;i++){

//初始化dist[]數組

dist[i]=a[v][i];

s[i]=false;

/*

*?prve[]數組存儲源點到頂點vi之間的最短路徑上該頂點的前驅頂點,

*?若從源點到頂點vi之間無法到達，則前驅頂點為-1

*/

if(dist[i]

prve[i]=v;

else

prve[i]=-1;

}

dist[v]=0;??????????//初始化v0源點屬于s集

s[v]=true;??????????//表示v0源點已經求得最短路徑

for(int?i=1;i<=n;i++){

int?temp=Integer.MAX_VALUE;?//temp暫存v0源點到vi頂點的最短路徑

int?u=v;

for(int?j=1;j<=n;j++){

if((!s[j])&&dist[j]

u=j;????????????????????????????????????????????//更新當前源點,當前vi作為下一個路徑的源點

temp=dist[j];???????????????????????????//更新當前最短路徑

}

}

s[u]=true;??????????????????????????????????????//頂點vi進s集

//更新當前最短路徑以及路徑長度

for(int?j=0;j<=n;j++){

if((!s[j])&&a[u][j]

int?newDist=dist[u]+a[u][j];????????????????????????????????//累加更新最短路徑

if(newDist

dist[j]=newDist;????????????????????????????????????????????????????//更新后的最短路徑

prve[j]=u;??????????????????????????????????????????????????????????//當前頂點加入前驅頂點集

}

}

}

}

}

//結果輸出方法

/*

*?m:源點

*?[]p:更新結果后的前驅頂點集

*?[]d:更新結果后的最短路徑集

*/

public?void?outPath(int?m,int?[]p,int?[]d){

for(int?i=0;i

//當前頂點已求得最短路徑并且當前頂點不等于源點

if(d[i]

System.out.print("v"+i+"

int?next=p[i];??????????????//設置當前頂點的前驅頂點

while(next!=m){?????//若前驅頂點不為一個，循環求得剩余前驅頂點

System.out.print("v"+next+"

next=p[next];

}

System.out.println("v"+m+":"+d[i]);

}

//當前頂點未求得最短路徑的處理方法

else

if(i!=m)

System.out.println("v"+i+"

}

}

public?static?void?main(String[]?args)?{

//?TODO?Auto-generated?method?stub

Dijkstra?D=new?Dijkstra();

D.dijkstra(0,?a,?dist,?prve);

D.outPath(0,?prve,?dist);

}

}

結果如下:

總結

以上是生活随笔為你收集整理的java 迪杰斯特拉_Java 实现Dikstra迪杰斯特拉算法 关于单源顶点最短路径问题的求解...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。