首页 > 代码库 > java实现floyd统计天津地铁的站点距离
java实现floyd统计天津地铁的站点距离
一:说明
(1)使用floyd实现各个站点的计算记录和路径
(2)站点获取和初始距离根据外部文件得到
(3)结果以外部文件的形式存储
(4)站点间转乘,认为初始值也为1
(5)代码注释比较详细,如有疑问或者代码有,请联系我,谢谢
(6)java中二维数据的定义:
a: float[][] numthree; //定义一个float类型的2维数组
numthree=new float[5][5]; //为它分配5行5列的空间大小
numthree[0][0]=1.1f; //通过下标索引去访问 1行1列=1.1
numthree[1][0]=1.2f; // 2行1列=1.2
b: int[][] numseven=new int[][]{{10,20,30},{40,50},{60}}; //没什么好说的如果你在看不懂 那就别学了!
c: list 二维数组: List<Object>[][]lists=new ArrayList[4][4];
存放二维对象类型的list二维数组: List<Object[][]>[][] list=new ArrayList[4][4];
存放二维数组的list: List<Object[][]> list=new ArrayList<Object[][]>()
(7)数组的遍历
a:
int arr[][] = new int[][] { { 1 }, { 1, 2 }, { 1, 2, 3 } }; for (int i = 0; i < arr.length; i++) { int[] arr2 = arr[i]; for (int c = 0; c < arr2.length; c++) { System.out.print(arr2[c]); }b: arr[i][j]的方式
c:
java 遍历arrayList的四种方法 package com.test; import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class ArrayListDemo { public static void main(String args[]){ List<String> list = new ArrayList<String>(); list.add("luojiahui"); list.add("luojiafeng"); //方法1 Iterator it1 = list.iterator(); while(it1.hasNext()){ System.out.println(it1.next()); } //方法2 for(Iterator it2 = list.iterator();it2.hasNext();){ System.out.println(it2.next()); } //方法3 for(String tmp:list){ System.out.println(tmp); } //方法4 for(int i = 0;i < list.size(); i ++){ System.out.println(list.get(i)); } } }
二:完整代码如下
package edu.tju.cs; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileInputStream; import java.io.FileWriter; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class MetroFloyd { private final int MAX_SIZE = 92;// 86+1 + 5个未开通的 数组的空间,可以再大一些 private int k = 0; private int Vertex = 0;// 站点个数,通过读取每一条记录得到 private int[] Line = new int[MAX_SIZE];// 和path一起记录路径的 private int[][] Path = new int[MAX_SIZE][MAX_SIZE];// 记录路径 private int[][] Dist = new int[MAX_SIZE][MAX_SIZE];//记录各个站点间距离的 private List<Integer> stationID = new ArrayList<Integer>();//得到站点编号 private Map<Integer,String> mapIDName = new HashMap<Integer,String>();// 站点编号和名称的对应关系 /* 功能:读取外部文件,把站点编号 放到stationID数组中,站点编号和名称的对应关系mapIDName,以及Vertex统计 * @param: originalPath 读文件件的路径名称 * @调用其他函数: null * @return: null */ // // 2305,刘园,117.123174,39.214493 public void readText(String originalPath){ try { Vertex = 0; String regex = ",";// 分割依赖符号,\ String encoding="GBK"; File file=new File(originalPath); if(file.isFile() && file.exists()){ //判断文件是否存在 InputStreamReader read = new InputStreamReader( new FileInputStream(file),encoding);//考虑到编码格式 BufferedReader bufferedReader = new BufferedReader(read); // 原始一行数据和数据是否需要改变的符号 String originalLine = null; originalLine = bufferedReader.readLine();// 第一行列标示符过滤掉 if(originalLine == null){ read.close(); bufferedReader.close(); return; } stationID.add(0); // 无效值,因为是从站点编号是从1开始的 while((originalLine = bufferedReader.readLine()) != null){ // 字符串分隔 String tmp[] = originalLine.split(regex); // 如果符合重新合成 stationID.add(Integer.parseInt(tmp[0])); mapIDName.put(Integer.parseInt(tmp[0]), tmp[1]); Vertex++; System.out.println("jilu:" + Vertex); } // 关闭写文件 read.close(); bufferedReader.close(); } else { System.out.println("找不到指定的文件"); } } catch (Exception e) { System.out.println("ReadToWrite……读取文件内容出错"); e.printStackTrace(); } System.out.println("ReadToWrite……Devide is over!!!"); } /* 功能:把各个站点的路径数和经过的路径统计出来,格式如下;仅仅是为了看齐效果:站点名称 * @param: destinationPath2 写文件件的路径名称 * @调用其他函数: null * @return: null * 结果示例: * ========================== Source:二纬路 Target:津湾广场 Distance:6 Path:二纬路-->海光寺-->鞍山道-->营口道-->营口道-->和平路-->津湾广场 ========================== */ // public void writeText2(String destinationPath2){ try { BufferedWriter bufferWriter = new BufferedWriter(new FileWriter(destinationPath2)); String newLine = ""; int p,q,m; for(p=1;p<=Vertex;p++) { for(q=p+1;q<=Vertex;q++) { newLine = "\n==========================\nSource:" + mapIDName.get(stationID.get(p)) + "\nTarget:" + mapIDName.get(stationID.get(q)) + "\nDistance:" + Dist[p][q] + "\nPath:" + mapIDName.get(stationID.get(p)); k=2; Root(p,q); for(m=2;m<=k-1;m++){ newLine = newLine + "-->" + mapIDName.get(stationID.get(Line[m])); } newLine += "\n==========================\n"; bufferWriter.write(newLine); } } bufferWriter.close(); } catch (Exception e) { System.out.println("MergeMinDistortByDay_Zheng……读取文件内容出错"); e.printStackTrace(); } } /* 功能:把各个站点的路径数和经过的路径统计出来,格式如下;仅仅是站点的编号,这是后面要用到的文件格式。 * @param: destinationPath2 写文件件的路径名称 * @调用其他函数:private void Root(int p,int q) 返回路径所经过的站点 * @return: null */ // 输出最短路径,仅仅编号之间的对应关系 2314,533 --> 2314,533,6,2314,2313,529,530,531,532,533 public void writeText(String destinationPath){ try { BufferedWriter bufferWriter = new BufferedWriter(new FileWriter(destinationPath)); String newLine = ""; int p,q,m; for(p=1;p<=Vertex;p++) { for(q=1;q<=Vertex;q++) { newLine = "" + stationID.get(p) + "," + stationID.get(q) + "," + Dist[p][q] + "," + stationID.get(p); k=2; Root(p,q); for(m=2;m<=k-1;m++){ newLine = newLine + "," + stationID.get(Line[m]); } newLine += "\n"; bufferWriter.write(newLine); } } bufferWriter.close(); } catch (Exception e) { System.out.println("MergeMinDistortByDay_Zheng……读取文件内容出错"); e.printStackTrace(); } } /* 功能:初始化各个站点间的初始距离,即相邻的为1,不相邻的为0,转乘车站坐特殊处理,且转乘车站之间认为路径是1 * @param: null * @调用其他函数: null * @return: null */ // init private void init(){ /*|| (stationID.get(p)==280 && 533-stationID.get(q) == 1) || (stationID.get(p)==280 && 791-stationID.get(q) == 1) || (stationID.get(p)==533 && 280-stationID.get(q) == 1) || (stationID.get(p)==533 && 791-stationID.get(q) == 1) || (stationID.get(p)==791 && 280-stationID.get(q) == 1) || (stationID.get(p)==791 && 533-stationID.get(q) == 1) || (stationID.get(q)==280 && 533-stationID.get(p) == 1) || (stationID.get(q)==280 && 791-stationID.get(p) == -1) || (stationID.get(q)==533 && 280-stationID.get(p) == -1) || (stationID.get(q)==533 && 791-stationID.get(p) == -1) || (stationID.get(q)==791 && 280-stationID.get(p) == -1) || (stationID.get(q)==791 && 533-stationID.get(p) == -1)*/ // 初始化 for(int p=1;p<=Vertex;p++){ for(int q=1;q<=Vertex;q++){// 280 533 791 tj if(stationID.get(p)-stationID.get(q)==-1 || stationID.get(p)-stationID.get(q)==1){ Dist[p][q] = 1; Dist[q][p] = 1; }else{ Dist[p][q] = 0; Dist[q][p] = 0; } Path[p][q] = 0; Path[p][q] = 0; } } // 营口道 转乘认为是一站地,13 78 得严格按照文件的顺序写,自己数数去 Dist[13][78]=1; Dist[78][13]=1; // 西南角 转乘认为是一站地 Dist[9][53]=1; Dist[53][9]=1; // 天津站 转乘认为是一站地 Dist[46][57]=1; Dist[57][46]=1; Dist[46][81]=1; Dist[81][46]=1; Dist[57][81]=1; Dist[81][57]=1; } /* 功能:递归函数的调用,计算路径所经过的站点时,会用到的 * @param: null * @调用其他函数: null * @return: null */ // 递归求各个路径上的点 private void Root(int p,int q){ if(Path[p][q]>0){ Root(p,Path[p][q]); Root(Path[p][q],q); }else{ Line[k]=q; k++; } } /* 功能:核心算法,floyd计算各个站点之间的路径 * @param: null * @调用其他函数: null * @return: null */ // floyd算法的计算最短路径 private void floyd() { int k,p,q; for(k=1;k<=Vertex;k++){ for(p=1;p<=Vertex;p++){ if(Dist[p][k]>0){ for(q=1;q<=Vertex;q++){ if(Dist[k][q]>0){ if(((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q)){ Dist[p][q]=Dist[p][k]+Dist[k][q]; Path[p][q]=k; } } } } } } } public static void main(String[] args){ MetroFloyd metroFloyd = new MetroFloyd(); // 2305,刘园,117.123174,39.214493 String originalPath = "D:\\tjdata_metro\\STATIONID_NAME_NEW.csv"; String destinationPath="D:\\tjdata_metro\\MetroFloydID.csv"; String destinationPath2="D:\\tjdata_metro\\MetroFloydName.csv"; metroFloyd.readText(originalPath); metroFloyd.init(); metroFloyd.floyd(); metroFloyd.writeText(destinationPath); metroFloyd.writeText2(destinationPath2); }
java实现floyd统计天津地铁的站点距离
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。