北京地下鉄路線計画
12176 ワード
一.プロジェクト紹介GitHubリンク：https://github.com/zhangyahui-0902/Subway コアアルゴリズム：Dijkstraアルゴリズム編纂言語：java需要分析：1.map subway.txt地下鉄路線情報2-a 1号線を路線名ですべてのサイト情報を取得する-o station.txtはこのテキストファイルに情報を書いて、3.bリンゴ園八宝山は両サイトを通じて最も短絡径-o rを獲得します。outine.txtは通過するサイトをこの文書ファイルに書く作業：1.subway.txtの情報を読み取り、それぞれのサイトの名前、所属回線、隣接サイトをそれぞれの回線に格納し、各回線も格納する。2.入力された回線名によって出力する。出発駅と終了サイトが存在するかどうかを調べる。出発駅と終了駅が同じかどうかなどの異常状況の処理
独立に完成できない原因：出発駅と終了駅を入力して、習ったディジ・ステラアルゴリズムに基づいて修正したいですが、もともと学んだのはマトリックス形式で記憶しています。長い間考えていますが、マトリックス形式をリスト形式に変えて最短パス計算法を完成することができませんでした。結局はアルゴリズムとlistに対する認識が足りないです。ファイル導入方式はsubway.txtフォーマットを設計します。
独立に完成できない原因：出発駅と終了駅を入力して、習ったディジ・ステラアルゴリズムに基づいて修正したいですが、もともと学んだのはマトリックス形式で記憶しています。長い間考えていますが、マトリックス形式をリスト形式に変えて最短パス計算法を完成することができませんでした。結局はアルゴリズムとlistに対する認識が足りないです。ファイル導入方式はsubway.txtフォーマットを設計します。
1
...File file=new File(path);
if(file.exists()) {
FileInputStream fl = new FileInputStream(file);
InputStreamReader br=new InputStreamReader(fl,"UTF-8");
BufferedReader reader=new BufferedReader(br);
String content="";
for(int i=0;i<22;i++) {
content=reader.readLine();
String[] lineArr=content.split(" ");
List line=new ArrayList();
String linename=lineArr[0];
for(int j=1;j linkedStations=line.get(j).getLinkStations();
if (j == 0) {
linkedStations.add(line.get(j + 1));
line.get(j).setLinkStations(linkedStations);
} else if (j == (line.size()-1) ) {
linkedStations.add(line.get(j - 1));
line.get(j).setLinkStations(linkedStations);
}else {
linkedStations.add(line.get(j+1));
linkedStations.add(line.get(j-1));
line.get(j).setLinkStations(linkedStations);
}
}
lineSet.add(line);
}
reader.close();
}
else
System.out.println(" ");
}
public class Station {
private String name;
private String line;
private List linkStations=new ArrayList<>();
}
public class Routine {
private Station begin;
private Station end;
private int distance=0;
private List passStations=new ArrayList<>();
}
if (!analysisList.contains(star)) {
analysisList.add(star);
}
if (resultMap.isEmpty()) {
List linkStations = getLinkStations(star);
for (Station station : linkStations) {
Routine routine = new Routine();
routine.setBegin(star);
routine.setEnd(station);
int distance = 1;
routine.setDistance(distance);
routine.getPassStations().add(station);
resultMap.put(station, routine);
}
}
Station parent = getNextStation();
if (parent == null) {
Routine routine = new Routine();
routine.setDistance(0);
routine.setBegin(star);
routine.setEnd(end);
return resultMap.put(end, routine);
}
if (parent.equals(end)) {
return resultMap.get(parent);
}
List childLinkStations = getLinkStations(parent);
for (Station child : childLinkStations) {
if (analysisList.contains(child)) {
continue;
}
int distance = 1+resultMap.get(parent).getDistance();
if (parent.getName().equals(child.getName())) {
distance = 0;
}
List parentPassStations = resultMap.get(parent).getPassStations();
Routine childResult = resultMap.get(child);
if (childResult != null) {
if (childResult.getDistance() > distance) {
childResult.setDistance(distance);
childResult.getPassStations().clear();
childResult.getPassStations().addAll(parentPassStations);
childResult.getPassStations().add(child);
}
} else {
childResult = new Routine();
childResult.setDistance(distance);
childResult.setBegin(star);
childResult.setEnd(child);
childResult.getPassStations().addAll(parentPassStations);
childResult.getPassStations().add(child);
}
resultMap.put(child, childResult);
}
analysisList.add(parent);
shortest(star, end);
return resultMap.get(end);
-map subway.txt-a 1 -map subway.txt -o station.txt-b -map subway.txt -o routine.txt if(args.length==2&&args[0].equals("-map"))
Subway.Data(args[1]);
else if(args.length==6&&args[0].equals("-a")&&args[2].equals("-map")&&args[4].equals("-o")) {
Subway.Data(args[3]);
writeRoute(args[1],args[5]);// station.txt
}
else if(args.length==7&&args[0].equals("-b")&&args[3].equals("-map")&&args[5].equals("-o")){
Subway.Data(args[4]);
Result(args[1],args[2],args[6]);
// routine.txt
}
else {
System.out.println(" ");
} List route=null;
int flag=1;
File file=new File(path);
FileWriter fw =new FileWriter(file);;
for(List l:Subway.lineSet){
flag=1;
for(Station s:l) {
if(!s.getLine().equals(linename))
flag=0;
}
if(flag==1) {
route=l;
}
}
if(route==null) {
fw.write(" ");
fw.close();
}
else {
if(file.exists()&&file.isFile()) {
try {
fw.write(linename);
fw.write("\r
");
for(Station s:route) {
fw.write(s.getName());//
fw.write("\r
");
}
fw.close();
} catch (IOException e) {
e.printStackTrace();
}
}
else
fw.write(" ");
fw.close();
} -a 1 -map subway.txt -o station.txt1
-a 2 -map subway.txt -o station.txt -a 1 -map subway.txt -m station.txt -c 1 -map subway.txt -o station.txt File file=new File(path);
Station b;
Station o;
FileWriter fw;
try {
fw=new FileWriter(file);
Routine routine;
b=Dijkstra.findStation(begin,Subway.lineSet);
o=Dijkstra.find(end,Subway.lineSet);
if(o!=null&&b!=null&&!o.getName().equals(b.getName())) {
routine=Dijkstra.shortest(b,o);
if(routine!=null) {
if(b.getLinkStations().contains(o)) {
fw.write("-> "+b.getLine());
fw.write("\r
");
fw.write(b.getName());
fw.write("\r
");
fw.write(o.getName());
fw.close();
}
else {
fw.write("-> "+routine.getPassStations().get(1).getLine());
fw.write("\r
");
fw.write(b.getName());
fw.write("\r
");
for(int i=0;i "+routine.getPassStations().get(i+1).getLine());
fw.write("\r
");
}
}
fw.write(o.getName());
fw.write("\r
");
fw.write(" "+routine.getPassStations().size());
fw.close();
}
}else {
fw.write(" ");
fw.close();
}
}
else if(b==null) {
fw.write(" ");
fw.close();
}
else if(o==null) {
fw.write(" ");
fw.close();
}
else if(begin.equals(end)) {
fw.write(" ");
fw.close();
}
}
catch (IOException e) {
e.printStackTrace();
}
} -b -map subway.txt -o routine.txt-> 1
-b -map subway.txt -o routine.txt-> 1
6-b -map subway.txt -o routine.txt-> 4
3-b -map subway.txt -o routine.txt-> 4
3-b -map subway.txt -o routine.txt-> 4
-> 7
7-b -map subway.txt -o routine.txt -b -map subway.txt -o routine.txt -b -map subway.txt -o routine.txt