最短路径 floyd java_java实现Floyd算法求最短路径
關(guān)于無向圖的最短路徑問題：
這個程序輸出：最短路徑矩陣
例如:W[0][5]=9?代表vo->v5的最短路徑為9
W=:
0?1?3?7?4?9
1?0?2?6?3?8
3?2?0?4?1?6
7?6?4?0?3?2
4?3?1?3?0?5
9?8?6?2?5?0
package?com.xh.Floyd;
import?java.util.ArrayList;
public?class?Floyd_01?{
public?static?int?M?=?Integer.MAX_VALUE;
public?static?int?MAXSUM(int?a,int?b){
return?(a!=M&&b!=M)?(a+b):M;
}
public?static?ArrayList?flody(Integer[][]?dist){
Integer[][]?path=new?Integer[6][6];//存儲的是從i->j經(jīng)過的最后一個節(jié)點
for?(int?i?=?0;?i?
for?(int?j?=?0;?j?
path[i][j]=i;
}
}
for(int?k=0;k<6;k++){
for?(int?i?=?0;?i?
for?(int?j?=?0;?j?
if(dist[i][j]>MAXSUM(dist[i][k],?dist[k][j])){
path[i][j]=path[k][j];//存儲的是從i->j經(jīng)過的最后一個節(jié)點
dist[i][j]=MAXSUM(dist[i][k],?dist[k][j]);
}
}
}
}
ArrayList?list?=new?ArrayList();
list.add(dist);
list.add(path);
return?list;
}
public?static?Integer[]?reverse(Integer[]?chain,int?count){
int?temp;
for(int?i=0,j=count-1;i
temp=chain[i];
chain[i]=chain[j];
chain[j]=temp;
}
return?chain;
}
public?static?void?display_path(ArrayList?list){
Integer[][]?dist=list.get(0);
Integer[][]?path=list.get(1);
Integer[]?chain=new?Integer[6];
System.out.println("orign->dist"+"?dist?"+"?path");
for?(int?i?=?0;?i?<6;?i++)?{
for?(int?j?=?0;?j?
if(i!=j){//只是避免了vi->vi的輸出
//輸出源到目的地
System.out.print("\n???"+(i)+"->"+(j)+"?????");
//輸出最短路徑的長度
if(dist[i][j]==M){
System.out.print("?NA?");
}else{
System.out.print(dist[i][j]+"??????");
int?count=0;
int?k=j;
do?{
k=chain[count++]=path[i][k];
}?while?(i!=k);
chain=reverse(chain,count);
//輸出路徑
System.out.print(chain[0]+"");
for(k=1;k
System.out.print("->"+(chain[k]));
}
System.out.print("->"+j);
}
}
}
}
}
public?static?void?main(String[]?args)?{
Integer[][]?dist?=?{
{?0,?1,?4,?M,?M,?M?},
{?1,?0,?2,?7,?5,?M?},
{?4,?2,?0,?M,?1,?M?},
{?M,?7,?M,?0,?3,?2?},
{?M,?5,?1,?3,?0,?6?},
{?M,?M,?M,?2,?6,?0?}?};//?建立一個權(quán)值矩陣
ArrayList??list=flody(dist);
display_path(list);
}
}
總結(jié)
以上是生活随笔為你收集整理的最短路径 floyd java_java实现Floyd算法求最短路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 安全设置不许可html,快捷指令提示安全
- 下一篇： python 多线程和协程结合_如何让