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 = " ========================== Source:" + mapIDName.get（stationID.get（p）） + " Target:" + mapIDName.get（stationID.get（q）） + " Distance:" + Dist[p][q] + " Path:" + 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 += " ========================== ";
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 += " ";
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中介者设计模式 http://www.linuxidc.com/Linux/2014-07/104319.htmJava 设计模式之模板方法开发中应用 http://www.linuxidc.com/Linux/2014-07/104318.htm设计模式之 Java 中的单例模式（Singleton） http://www.linuxidc.com/Linux/2014-06/103542.htmJava对象序列化 http://www.linuxidc.com/Linux/2014-10/107584.htm大话设计模式（带目录完整版） PDF+源代码 http://www.linuxidc.com/Linux/2014-08/105152.htmJava中的函数传递 http://www.linuxidc.com/Linux/2014-11/109056.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-11/109353.htm