佛洛依德算法问题 算法java数据结构佛洛依德floyd 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 因为代码有错误。给你一个正确的实现,自己对照下:import java.util.ArrayList; import java.util.List; public class FloydInGraph { private static int max=Integer.MAX_VALUE; //dist[i][j]=max<==>i 和 j之间没有边 private int[][] dist; //顶点i 到 j的最短路径长度,初值是i到j的边的权重 private int[][] path; private List< Integer> result=new ArrayList< Integer>(); public static void main(String[] args) { FloydInGraph graph=new FloydInGraph(6); int[][] matrix={ {max,max,10,max,30,100}, {max,max,5,max,max,max}, {max,max,max,50,max,max}, {max,max,max,max,20,10}, {max,max,max,max,max,60}, {max,max,max,max,max,max} }; for(int i=0;i<6;i++) for(int j=0;j<6;j++) { graph.findCheapestPath(i,j,matrix); List< Integer> list=graph.result; System.out.print(i+" to "+j+",the cheapest path is: "); if(max==graph.dist[i][j]) { System.out.println("There is no path from "+i+" to "+j); } else { System.out.println(list.toString()); System.out.println("path distance: "+graph.dist[i][j]); } } } public void findCheapestPath(int begin,int end,int[][] matrix){ floyd(matrix); result.clear(); result.add(begin); findPath(begin,end); result.add(end); } public void findPath(int i,int j){ int k=path[i][j]; if(k==-1)return; findPath(i,k); result.add(k); findPath(k,j); } public void floyd(int[][] matrix){ int size=matrix.length; for(int i=0;i< size;i++){ for(int j=0;j< size;j++){ path[i][j]=-1; dist[i][j]=matrix[i][j]; } } for(int k=0;k< size;k++){ for(int i=0;i< size;i++){ for(int j=0;j< size;j++){ if(dist[i][k]!=max&& dist[k][j]!=max&& dist[i][k]+dist[k][j]< dist[i][j]){ dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=k; } } } } } public FloydInGraph(int size){ this.path=new int[size][size]; this.dist=new int[size][size]; } } ArrayList排序问题 做java安装哪个版本linux比较好?新手求助,谢谢! 创建xml时,设置xml编码问题??急急急 WFQ 算法的java实现 java字符长度问题 寻求一解决思路(关于javaIO方面的) 小弟第一次写java应用程序,问题多多,help!,要分的大虾尽管来(在线等!!!)谢谢啦 如何在jdbtable中加入组合框(给50) 字体难看怎么办? 谁能给我一个最简单的回答,关于事件响应的。 求多数组的排列组合算法 java泛型问题
import java.util.List; public class FloydInGraph {
private static int max=Integer.MAX_VALUE; //dist[i][j]=max<==>i 和 j之间没有边
private int[][] dist; //顶点i 到 j的最短路径长度,初值是i到j的边的权重
private int[][] path;
private List< Integer> result=new ArrayList< Integer>();
public static void main(String[] args) {
FloydInGraph graph=new FloydInGraph(6);
int[][] matrix={
{max,max,10,max,30,100},
{max,max,5,max,max,max},
{max,max,max,50,max,max},
{max,max,max,max,20,10},
{max,max,max,max,max,60},
{max,max,max,max,max,max}
};
for(int i=0;i<6;i++)
for(int j=0;j<6;j++)
{
graph.findCheapestPath(i,j,matrix);
List< Integer> list=graph.result;
System.out.print(i+" to "+j+",the cheapest path is: ");
if(max==graph.dist[i][j])
{
System.out.println("There is no path from "+i+" to "+j);
}
else
{
System.out.println(list.toString());
System.out.println("path distance: "+graph.dist[i][j]);
}
}
}
public void findCheapestPath(int begin,int end,int[][] matrix){
floyd(matrix);
result.clear();
result.add(begin);
findPath(begin,end);
result.add(end);
}
public void findPath(int i,int j){
int k=path[i][j];
if(k==-1)return;
findPath(i,k);
result.add(k);
findPath(k,j);
}
public void floyd(int[][] matrix){
int size=matrix.length;
for(int i=0;i< size;i++){
for(int j=0;j< size;j++){
path[i][j]=-1;
dist[i][j]=matrix[i][j];
}
}
for(int k=0;k< size;k++){
for(int i=0;i< size;i++){
for(int j=0;j< size;j++){
if(dist[i][k]!=max&&
dist[k][j]!=max&&
dist[i][k]+dist[k][j]< dist[i][j]){
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=k;
}
}
}
}
}
public FloydInGraph(int size){
this.path=new int[size][size];
this.dist=new int[size][size];
}
}