手机版
你好,游客 登录 注册
背景:
阅读新闻

Java实现Floyd统计天津地铁的站点距离

[日期:2014-11-13] 来源:Linux社区  作者:瞭望天空 [字体: ]

一:说明

(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

本文永久更新链接地址http://www.linuxidc.com/Linux/2014-11/109353.htm

linux
相关资讯       Floyd 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款