travel.java

旅游路线方案程序 弗洛伊德算法的实现 java版

package 旅游行程方案;

import java.io.*;
import java.util.StringTokenizer;

public class Travel {
	public static LList city = new LList();// 存放城市信息，每个元素为一个String类表示的城市

	public static LList lcity1 = new LList();// 存放最短路径信息，每个元素为一个String类表示的城市

	public static LList lcity2 = new LList();// 存放最快路径信息，每个元素为一个String类表示的城市

	public static String[] cityarray;// 数组表示的城市信息（由于FloydPath()方法中需要数组表示）

	public static String[] necityarray;// 数组表示的邻近的城市信息

	public static Graphm graph1;// 1：考虑路程

	public static Graphm graph2;// 2：考虑时间

	static int[][] distance1;// 存放任意两城市间的最短路程

	static int[][] distance2;// 存放任意两城市间的最快时间

	static int[][] dist1;// 为记录路径而设的二维数组，dist[i][j]初为-1，经Floyd()算法改变，用于FloydPath()算法中。

	static int[][] dist2;// 考虑时间，用途同dis1

	public static void main(String[] args) {
		try {
			File file = new File("./cityinformation.txt");
			FileReader fr = new FileReader(file);
			BufferedReader br = new BufferedReader(fr);
			String s = br.readLine();// 每行读入的字符串
			StringTokenizer st;
			s = br.readLine();
			while (!s.equals("PATHS")) { // 读取城市名信息，存入city
				st = new StringTokenizer(s, "###");
				st.nextToken();
				city.append(st.nextToken());
				s = br.readLine();
			}
			graph1 = new Graphm(city.length());// 建立图
			graph2 = new Graphm(city.length());
			distance1 = new int[city.length()][city.length()];
			distance2 = new int[city.length()][city.length()];
			dist1 = new int[city.length()][city.length()];
			dist2 = new int[city.length()][city.length()];
			for (int i = 0; i < city.length(); i++)
				for (int j = 0; j < city.length(); j++) {
					dist1[i][j] = -1;
					dist2[i][j] = -1;
				}
			s = br.readLine();
			while (s != null) { // 读取城市间路程等信息，存入graph1,graph2
				st = new StringTokenizer(s, "###");
				int a1 = Integer.parseInt(st.nextToken().toString());// 城市1
				int a2 = Integer.parseInt(st.nextToken().toString());// 城市2
				int lucheng = Integer.parseInt(st.nextToken().toString());// 路程
				int sudu = Integer.parseInt(st.nextToken().toString());// 速度
				int shijian = lucheng / sudu;// 时间
				graph1.setEdge(a1 - 1, a2 - 1, lucheng);
				graph1.setEdge(a2 - 1, a1 - 1, lucheng);
				graph2.setEdge(a1 - 1, a2 - 1, shijian);
				graph2.setEdge(a2 - 1, a1 - 1, shijian);
				s = br.readLine();
			}
			cityarray = toarray(city);// 为cityarray赋值
			Floyd1(graph1, distance1);
			Floyd2(graph2, distance2);
			String city1 = null;// 起始城市名
			String city2 = null;// 终点城市名
			System.out.println("请输入起始城市名：");
			try {
				BufferedReader in = new BufferedReader(new InputStreamReader(
						System.in));
				city1 = in.readLine();
			} catch (IOException e) {
			}
			System.out.println("请输入终点城市名：");
			try {
				BufferedReader in = new BufferedReader(new InputStreamReader(
						System.in));
				city2 = in.readLine();
			} catch (IOException e) {
			}
			System.out.println();
			int a = cityno(cityarray, city1);
			int b = cityno(cityarray, city2);
			String str1;// 输出的结果
			String str2;
			String str3 = "";
			str1 = city1;
			FloydPath1(dist1, a, b);
			for (lcity1.setFirst(); lcity1.isInList(); lcity1.next()) {
				str1 = str1 + "--->" + lcity1.currValue().toString();
			}
			str1 = str1 + "--->" + city2;
			System.out.println(city1 + "到" + city2 + "的最短路程为:"
					+ distance1[a][b]);
			System.out.println("路线：" + str1);
			str2 = city1;
			FloydPath2(dist2, a, b);
			for (lcity2.setFirst(); lcity2.isInList(); lcity2.next()) {
				str2 = str2 + "--->" + lcity2.currValue().toString();
			}
			str2 = str2 + "--->" + city2;
			System.out.println(city1 + "到" + city2 + "的最快时间为:"
					+ distance2[a][b]);
			System.out.println("路线：" + str2);
			nearCity(cityarray, graph1, cityarray[a].toString());
			for (int i = 0; i < necityarray.length; i++) {
				str3 = str3 + necityarray[i] + "  ";
			}
			System.out.println(city1 + "的相邻城市有：");
			System.out.println(str3);
		} catch (FileNotFoundException e) {
			System.out.print("FileNotFoundException" + e);
		} catch (IOException e) {
			System.out.println("IOException thrown:" + e);
		}
	}

	static String[] toarray(LList list) { // 用数组表示城市信息
		String[] cityarray = new String[list.length()];
		int i = 0;
		for (list.setFirst(); list.isInList(); list.next()) {
			cityarray[i] = list.currValue().toString();
			i++;
		}
		return cityarray;
	}

	static void nearCity(String[] allcity, Graphm c, String acity) { // 求acity的相邻城市，并按到acity的距离排序
		LList necity = new LList();
		for (int i = 0; i < city.length(); i++) {
			if (c.weight(cityno(allcity, acity), i) != 0
					&& c.weight(cityno(allcity, acity), i) != Integer.MAX_VALUE)
				necity.append(allcity[i]);
		}
		necity.setFirst();
		necityarray = toarray(necity);
		for (int i = 0; i < necity.length(); i++) {
			for (int j = i; (j > 0)
					&& (c.weight(cityno(allcity, acity), cityno(allcity,
							necityarray[j])) < c.weight(cityno(allcity, acity),
							cityno(allcity, necityarray[j - 1]))); j--) {
				String temp1 = necityarray[j];
				necityarray[j] = necityarray[j - 1];
				necityarray[j - 1] = temp1;
			}
		}
	}

	static int cityno(String[] cities, String city) { // 返回city的数组序号，cities为所有城市
		int j = 0;
		for (int i = 0; i < cities.length; i++) {
			if (cities[i].equals(city)) {
				j = i;
				break;
			}
		}
		return j;
	}

	static void Floyd1(Graphm G, int[][] D) { // 求最短路程算法，D[i][j]为i到j的最短路程
		for (int i = 0; i < G.n(); i++)
			for (int j = 0; j < G.n(); j++)
				if (i == j)
					D[i][j] = 0;
				else
					D[i][j] = G.weight(i, j);
		for (int k = 0; k < G.n(); k++)
			for (int i = 0; i < G.n(); i++)
				for (int j = 0; j < G.n(); j++)
					if ((D[i][k] != Integer.MAX_VALUE)
							&& (D[k][j] != Integer.MAX_VALUE)
							&& (D[i][j] > D[i][k] + D[k][j])) {
						dist1[i][j] = k;
						D[i][j] = D[i][k] + D[k][j];
					}
	}

	static void Floyd2(Graphm G1, int[][] D1) {
		for (int i = 0; i < G1.n(); i++)
			for (int j = 0; j < G1.n(); j++)
				if (i == j)
					D1[i][j] = 0;
				else
					D1[i][j] = G1.weight(i, j);
		for (int k = 0; k < G1.n(); k++)
			for (int i = 0; i < G1.n(); i++)
				for (int j = 0; j < G1.n(); j++)
					if ((D1[i][k] != Integer.MAX_VALUE)
							&& (D1[k][j] != Integer.MAX_VALUE)
							&& (D1[i][j] > D1[i][k] + D1[k][j])) {
						dist2[i][j] = k;
						D1[i][j] = D1[i][k] + D1[k][j];
					}
	}

	public static void FloydPath1(int[][] path, int i, int j) {// 记录最短路径算法，把i到j的最短路径信息传给lcity1
		if (path[i][j] != -1) {
			FloydPath1(path, i, path[i][j]);
			lcity1.append(cityarray[path[i][j]]);
			FloydPath1(path, path[i][j], j);
		}
		return;
	}

	public static void FloydPath2(int[][] path, int i1, int j1) {
		if (path[i1][j1] != -1) {
			FloydPath2(path, i1, path[i1][j1]);
			lcity2.append(cityarray[path[i1][j1]]);
			FloydPath2(path, path[i1][j1], j1);
		}
		return;
	}
}