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)数组的遍历

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]的方式

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统计天津地铁的网站距离

最新文章

热门文章