图中任意两点间所有路径高效算法

算法中将一条线视为一个结点，采用广度优先搜索，利用树结构存储搜索结果，算法效率高，在武汉地铁11条线路190余个站点的线网图中测试，任意两点间的所有路径平均耗时0.2秒。只要对算法中的费用矩阵做调整，即可适用于公交等其他网络。

package com.bean;

import java.util.ArrayList;
import java.util.List;

public class Line {

	private int id; //线路id
	private List stationList = new ArrayList（）;//本条线的车站列表
	private boolean isCircle ;//是否为环线

	public int getId（） {
		return id;
	}
	public void setId（int id） {
		this.id = id;
	}
	
	public List getStationList（） {
		return stationList;
	}
	public void setStationList（List stationList） {
		this.stationList = stationList;
	}
	public boolean isCircle（） {
		return isCircle;
	}
	public void setCircle（boolean isCircle） {
		this.isCircle = isCircle;
	}
	
	public Station getStation（int id）
	{
		for（Station sta : stationList）
		{
			if（sta.getId（）==id）
			{
				return sta;
			}
		}
		return null;
	}
	
	
	public List> getPathInLine（int startStaIdint endStaId）
	{
		
		List result1 = new ArrayList（）;
		List result2 = new ArrayList（）;
		result1.add（startStaId）;
		result2.add（startStaId）;
		
		int temp = startStaId;
		while（temp!=endStaId && getStation（temp）.getNextSta（）!=null）
		{
			Station sta = getStation（temp）;
			temp = sta.getNextSta（）.getId（）;
			result1.add（temp）;
			
		}
		temp = startStaId;
		while（temp!=endStaId & getStation（temp）.getPrevSta（）!=null）
		{
			Station sta = getStation（temp）;
			temp = sta.getPrevSta（）.getId（）;
			result2.add（temp）;
			
		}
		
		List> result = new ArrayList>（）;
		if（result1.get（result1.size（）-1） == endStaId）
		{
			result.add（result1）;
		}
		if（result2.get（result2.size（）-1） == endStaId）
		{
			result.add（result2）;
		}
		return result;
	}
	public Station getStation（String name） {
		// TODO Auto-generated method stub
		for（Station sta : stationList）
		{
			if（sta.getName（）.equals（name））
			{
				return sta;
			}
		}
		
		return null;
	}
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        422  2018-07-27 18:51  PathSearch\.classpath

     文件        386  2018-04-13 13:11  PathSearch\.project

     文件        598  2018-04-13 13:11  PathSearch\.settings\org.eclipse.jdt.core.prefs

     文件       2987  2018-07-28 11:20  PathSearch\bin\com\bean\Line.class

     文件        611  2018-07-28 11:20  PathSearch\bin\com\bean\SolutionTree.class

     文件       2073  2018-07-28 11:20  PathSearch\bin\com\bean\Station.class

     文件       5166  2018-07-28 11:18  PathSearch\bin\com\bean\TreeNode.class

     文件       1513  2018-07-28 11:15  PathSearch\bin\com\main\Enter.class

     文件      15449  2018-07-27 21:01  PathSearch\bin\com\main\PathSearch.class

     文件       4403  2018-07-27 18:51  PathSearch\bin\com\tools\MyDatabase.class

     文件     724225  2018-04-13 01:33  PathSearch\mysql-connector-java-5.1.10-bin.jar

     文件       1926  2018-07-28 11:20  PathSearch\src\com\bean\Line.java

     文件        287  2018-07-28 11:20  PathSearch\src\com\bean\SolutionTree.java

     文件       1223  2018-07-28 11:20  PathSearch\src\com\bean\Station.java

     文件       5980  2018-07-28 11:18  PathSearch\src\com\bean\TreeNode.java

     文件        715  2018-07-28 11:15  PathSearch\src\com\main\Enter.java

     文件      18239  2018-07-27 21:01  PathSearch\src\com\main\PathSearch.java

     文件       2337  2018-04-13 01:30  PathSearch\src\com\tools\MyDatabase.java

     目录          0  2018-07-28 11:11  PathSearch\bin\com\bean

     目录          0  2018-07-28 11:11  PathSearch\bin\com\main

     目录          0  2018-07-28 11:12  PathSearch\bin\com\tools

     目录          0  2018-07-28 11:11  PathSearch\src\com\bean

     目录          0  2018-07-28 11:11  PathSearch\src\com\main

     目录          0  2018-07-28 11:12  PathSearch\src\com\tools

     目录          0  2018-07-28 11:11  PathSearch\bin\com

     目录          0  2018-07-28 11:11  PathSearch\src\com

     目录          0  2018-04-13 13:11  PathSearch\.settings

     目录          0  2018-07-27 18:51  PathSearch\bin

     目录          0  2018-04-13 13:12  PathSearch\src

     目录          0  2018-07-27 15:52  PathSearch

............此处省略3个文件信息