地铁出行线路规划
Github：31701021
代码链接：https://github.com/31701021/31701021wyd/tree/subway
一、设计思路
1.利用文本文档形式储存地铁线路信息
2.读入数据并建立邻接列表
3.使用dijkstra算法查找最短路径
二、文本文档储存形式
1号线
23
苹果园
古城
八角游乐园
......
2号线
18
积水潭
鼓楼大街
安定门
......
三、程序设计
程序一个创建了四个类，分别是Main，node，edge和passedPath。
node类是用来储存站点的信息
public class node {
private String id;
private List<String> line;
private List<edge> edges;
node(){
line=new ArrayList<>();
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public List<String> getLine() {
return line;
}
public void setLine(List<String> line) {
this.line = line;
}
public List<edge> getEdges() {
return edges;
}
public void setEdges(List<edge> edges) {
this.edges = edges;
}
} 其中id是站点名字，line是站点所在线路，edges是站点所在边。
edge类是用来储存边的信息
public class edge {
private String startNodeId;
private String endNodeId;
public final int weight=1;
public String getStartNodeId() {
return startNodeId;
}
public void setStartNodeId(String startNodeId) {
this.startNodeId = startNodeId;
}
public String getEndNodeId() {
return endNodeId;
}
public void setEndNodeId(String endNodeId) {
this.endNodeId = endNodeId;
} 其中startNodeId和endNodeId分别是该边的两个站点，weight是距离，默认为1。
passedPath类是用来储存站到站的线路信息
public class passedPath {
private node curNode ; //当前站点
private boolean visited ; //是否已被处理
private Integer weight ; //累积的权值
private List<String> passedIDList ; //路径
passedPath(node id){
this.curNode = id;
this.weight = Integer.MAX_VALUE; //初始化时假设每个节点到源节点的距离为无穷大
this.passedIDList = new ArrayList<String>();
this.visited = false;
}
passedPath(){
this.curNode = null;
this.weight = Integer.MAX_VALUE;
this.passedIDList = new ArrayList<String>();
this.visited = false;
}
public node getCurNode() {
return curNode;
}
public void setCurNode(node curNode) {
this.curNode = curNode;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public Integer getWeight() {
return weight;
}
public void setWeight(Integer weight) {
this.weight = weight;
}
public List<String> getPassedIDList() {
return passedIDList;
}
public void setPassedIDList(List<String> passedIDList) {
this.passedIDList = passedIDList;
}Main是用来执行根据用户输入的指令的各种操作，其中包含以下几个重要函数
//dijkstra算法
public static void run(List<node> V){
passedPath min = new passedPath();//使用无参数的
int flag=0;
for(passedPath c:paths){
if(!c.isVisited()){
if(c.getWeight()<min.getWeight()){
min = c;
}
flag++;
}
}
if(flag==0) return;
//用min去更新可达节点的path
for(edge c:min.getCurNode().getEdges()){
//根据目标节点名找到目标节点的passedPath:to
node tmp=null;
for(node d:V){
if(d.getId().equals(c.getEndNodeId())){
tmp = d;
}
}
passedPath to=null;
for(passedPath e:paths){
if(e.getCurNode().equals(tmp)){
to = e;
}
}
if(to.getWeight()>c.weight+min.getWeight()){
List<String> tmpList = new ArrayList<String>(min.getPassedIDList());
tmpList.add(to.getCurNode().getId());
to.setPassedIDList(tmpList); //更新路径列表
to.setWeight(c.weight+min.getWeight()); //更新累积权值
}
}
min.setVisited(true);
run(V);
}
//读入并初始化站点信息
public static void initnodes(String path) throws IOException {
InputStreamReader reader = new InputStreamReader (new FileInputStream(path),"UTF-8");
BufferedReader bufferedReader = new BufferedReader(reader);
String line =bufferedReader.readLine();//读入线路
while (line!=null){
int num =Integer.parseInt(bufferedReader.readLine());//读入线路站数
String prenode=null;
String curnode=bufferedReader.readLine();
for(int i=1;i<=num;i++) {
node node=new node();
node.setId(curnode);
node.getLine().add(line);
nodes1.add(node);
if(prenode!=null)
nears.add(prenode);
prenode=curnode;
if(i!=num) {
curnode=bufferedReader.readLine();
nears.add(curnode);
}
init(prenode,nears,line);
nears.clear();
}
line=bufferedReader.readLine();
}
bufferedReader.close();
reader.close();
System.out.println("读取成功");
}
public static void init(String id,List<String> nears,String line){
int flag=0;
int index=0;
for(node node:nodes) {
if(node.getId().equals(id)) {
flag=1;
index=nodes.indexOf(node);
}
}
if(flag==0) {
node tmp = new node();
tmp.setId(id);
tmp.getLine().add(line);
edge tmp_ = null;
List<edge> edges = new ArrayList<edge>();
for(String near:nears){
tmp_ = new edge();
tmp_.setStartNodeId(id);
tmp_.setEndNodeId(near);
edges.add(tmp_);
}
tmp.setEdges(edges);
nodes.add(tmp);
}
else {
node node =nodes.get(index);
node.getLine().add(line);
edge tmp_ = null;
for(String near:nears){
tmp_ = new edge();
tmp_.setStartNodeId(id);
tmp_.setEndNodeId(near);
node.getEdges().add(tmp_);
}
}
}
public static void initPath(List<node> V,String V0){
paths = new ArrayList<passedPath>();
passedPath path = null;
for(node c:V){
if(c.getId().equals(V0)){
path = new passedPath(c);
path.setWeight(0);
List<String> tmp = new ArrayList<String>();
tmp.add(V0);
path.setPassedIDList(tmp);
}else{
path = new passedPath(c);
}
paths.add(path);
}
}等等，以上并不完全。具体代码在github上。
四、具体操作
请将subway.txt放在subway\src目录下，其他四个文件放在subway\src\test目录下,并在subway\src\test目录下编译四个java文件，在subway\src目录下执行以下命令
读取地铁站点信息
java test.Main -map subway.txt读取并查询某条线路的站点
例如
java test.Main -map subway.txt -a 1号线读取并查询两个站点之间的最短路径
例如
java test.Main -map subway.txt -b 大望路 和平门
在上述命令后面增加 -o 文件名.txt，可创建文件名.txt并将查询结果写入文件名.txt中。
例如
java test.Main -map subway.txt -b 大望路 和平门 -o r.txt五、个人小结
经过这次个人作业，我了解到了自己的很多不足之处，无论是在算法上，还是设计上，我都还有许多需要提升的东西，本次作业的核心算法借鉴了网上的一些代码，再添加了一些修改。但是我觉得收获还是相当多的，接下来也要继续努力。