数据结构课程设计——校园导游

用无向网表示校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。  基本要求：  ① 查询任意景点的相关信息； ② 查询图中任意两个景点间的最短路径。 ③ 查询图中任意两个景点间的所有路径。 ④ 增加、删除、更新有关景点和道路的信息。 （选作）* 求多个景点的最佳（最短）游览路径。 带图形界面，动态标记路线，95分的课设

package com.schoolguider.algorithms;

import java.util.ArrayList;

import com.schoolguider.components.Node;
import com.schoolguider.utility.Manager;

/**
 * 双调欧几里得旅行商问题
 * 
 * @author xing
 *
 */
public class TSP {
	/**
	 * 用来获取结点和边的管理类
	 */
	private Manager manager;
	/**
	 * 景点的个数
	 */
	private int num = 0;
	/**
	 * 存储最短路径
	 */
	private double d[][];
	/**
	 * 存储任意两个结点之间的直线距离
	 */
	private double p[][];
	/**
	 * 存储结点的数组
	 */
	private TSPNode[] tspNodeArray;
	/**
	 * 存储路径
	 */
	private int kay[][];

	public TSP（Manager manager） {
		this.manager = manager;
		init（）;
		qsort（1 num）;
		getAllDis（）;
	}

	/**
	 * 初始化数据，为算法做准备
	 */
	private void init（） {
		ArrayList nodeList = manager.getNodeList（）;
		num = nodeList.size（）;
		tspNodeArray = new TSPNode[num + 1];
		d = new double[num + 1][num + 1];
		p = new double[num + 1][num + 1];
		kay = new int[num + 1][num + 1];
		/*
		 * 构造结点数组
		 */
		for （int i = 1; i <= num; i++） {
			Node node = nodeList.get（i-1）;
			int x = node.getX（）;
			int y = node.getY（）;
			tspNodeArray[i] = new TSPNode（x y）;
		}

		getAllDis（）;
	}

	/**
	 * 计算两点之间的直线距离
	 * 
	 * @param x1
	 * @param y1
	 * @param x2
	 * @param y2
	 * @return
	 */
	private double getDistance（int x1 int y1 int x2 int y2） {
		int x = （x1 - x2） * （x1 - x2）;
		int y = （y1 - y2） * （y1 - y2）;
		return Math.sqrt（x + y）;
	}

	/**
	 * 计算所有的道路的长度
	 */
	private void getAllDis（） {
		for （int i = 1; i < num; i++）
			for （int j = i + 1; j <= num; j++）
				p[i][j] = p[j][i] = getDistance（tspNodeArray[i].getX（）
						tspNodeArray[i].getY（） tspNodeArray[j].getX（）
						tspNodeArray[j].getY（））;
	}

	/**
	 * 快速排序的算法
	 * 
	 * @param l
	 * @param r
	 */
	private void qsort（int l int r） {
		/*
		 * 利用移位操作获取终点坐标
		 */
		int i = l j = r mid = tspNodeArray[（i + j） >> 1].getX（）;
		while （i < j） {
			while （tspNodeArray[i].getX（） < mid）
				i++;
			while （mid < tspNodeArray[j].getX（））
				j--;
			if （i <= j） {
				/*
				 * 交换两个结点的x坐标和y坐标
				 */
				swap（tspNodeArray[i].getX（） tspNodeArray[j].getX（））;
				swap（tspNodeArray[i].getY（） tspNodeArray[j].getY（））;
				i++;
				j--;
			}
		}
		/*
		 * 将原来的数组分为两部分继续递归
		 */
		if （l < j）
			qsort（l j）;
		if （i < r）
			qsort（i r）;
	}

	/**
	 * 交换两个数的值
	 * 
	 * @param x
	 * @param y
	 */
	private void swap（int x int y） {
		int temp = x;
		x = y;
		y = temp;
	}

	/**
	 * 动态规划计算最短路径
	 */
	public double DP（） {
		d[1][2] = p[1][2];// 最小的子问题

		for （int j = 3; j <= num; j++） {
			// i=1时的情况
			for （int i = 1; i < j - 1; i++） {
				d[i][j] = d[i][j - 1] + p[j - 1][j];
				kay[i][j] = j - 1;
			}
			// i=j-1的情况
			d[j - 1][j] = d[1][j - 1] + p[1][j];// 先设初值为kay=1时的值
			kay[j - 1][j] = 1;
			/*
			 * 从头到尾进行遍历
			 */
			for （int k = 1; k < j - 1; k++） {
				double q = d[k][j - 1] + p[k][j];
				if （q < d[j - 1][j]） {
					d[j - 1][j] = q;
					kay[j - 1][j] = k

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-01-19 21:07  SchoolGuider3.1\
     文件         402  2016-01-19 21:07  SchoolGuider3.1\.classpath
     文件         391  2016-01-19 21:07  SchoolGuider3.1\.project
     目录           0  2016-01-19 21:07  SchoolGuider3.1\.settings\
     文件         598  2016-01-19 21:07  SchoolGuider3.1\.settings\org.eclipse.jdt.core.prefs
     目录           0  2016-01-19 21:07  SchoolGuider3.1\bin\
     目录           0  2016-01-19 21:07  SchoolGuider3.1\bin\com\
     目录           0  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\
     目录           0  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\algorithms\
     文件        3733  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\algorithms\TSP.class
     文件         715  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\algorithms\TSPNode.class
     文件        3196  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\algorithms\TwoAllPath.class
     文件        2311  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\algorithms\TwoShortPath.class
     目录           0  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\
     文件         752  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\Addframe$1.class
     文件        2037  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\Addframe$2.class
     文件        2777  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\Addframe$3.class
     文件        6141  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\Addframe.class
     文件       12079  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\DisplayPanel.class
     文件        1124  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\ImagePane.class
     文件         475  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\MainClient.class
     文件        3144  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\Mainframe.class
     文件         811  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$1.class
     文件        1111  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$2.class
     文件        1211  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$3.class
     文件         939  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$4.class
     文件        2690  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$5.class
     文件        2719  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$6.class
     文件        1537  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$7.class
     文件        1118  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$8.class
     文件        1930  2016-01-19 21:07  SchoolGuider3.1\bin\com\schoolguider\client\OperationPanel$9.class
............此处省略58个文件信息