一:說明
(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中介者設計模式 http://www.linuxidc.com/Linux/2014-07/104319.htm
Java 設計模式之模板方法開發中應用 http://www.linuxidc.com/Linux/2014-07/104318.htm
設計模式之 Java 中的單例模式(Singleton) http://www.linuxidc.com/Linux/2014-06/103542.htm
Java對象序列化 http://www.linuxidc.com/Linux/2014-10/107584.htm
大話設計模式(帶目錄完整版) PDF+源代碼 http://www.linuxidc.com/Linux/2014-08/105152.htm
Java中的函數傳遞 http://www.linuxidc.com/Linux/2014-11/109056.htm