图的最短路径java_地铁线路最短路径（JAVA实现）

项目综述

提供一副地铁线路图&＃xff0c;计算指定两站之间最短(最少经过站数)乘车路线&＃xff1b;输出指定地铁线路的所有站点。以北京地铁为例&＃xff0c;地铁线路信息保存在data.txt中&＃xff0c;格式如下&＃xff1a;

地铁线路总数

线路名1 站名1 站名2 站名3 ...

线路名2 站名1 站名2 站名3 ...

线路名3 站名1 站名2 站名3 ......

一、需求分析

1.该程序能够准确地读出.txt文件中的数据&＃xff0c;文件格式简洁易懂、可灵活扩展

2.在某号线路上&＃xff0c;能够查询各个站点的信息&＃xff0c;输出该号线路上所有站点信息

3.在出发站与目的站之间输出一个最短路径

二、实现语言

Java

三、实现算法

Floyd算法

四、类职责划分

1.SubwayAssistantStarter类

程序入口

2.GetData类

从data.txt中读取数据并存储各条线路和各个站点

3.Line类

privateString name;private List stations &＃61; new ArrayList();//该线路上的所有站点

//已省略Getter & Setter

4.Map类

private int[][] subwayline;//存储线路private static List stations;//存储所有站点private int[][] path;//存储路径

//已省略Getter & Setter

5.Result类

private static final int max &＃61; 999999;//最大距离

private int[][] ShortestPath;//最短路径

private int[][] ShortestDis;//最短距离

//已省略Getter & Setter

6.FrmMain类

ui主界面&＃xff0c;包括功能选择和显示北京地铁线路背景图

7.FrmLine类 & FrmShowStations类

ui分页面

FrmLine类&＃xff1a;用户需输入格式正确的线路名

FrmShowStation类&＃xff1a;用户输入格式正确的线路名后弹窗显示具体线路信息

8.FrmShortestPath类 & FrmShowShortestPath类

ui分页面

FrmShortestPath类&＃xff1a;用户输入格式正确的站点名

FrmShowShortestPath类&＃xff1a;用户输入正确后弹窗显示两站间最短路径具体信息

五、核心代码

1.读取data.txt中的数据

public class GetData {//读取.txt文件中的信息

public static int linenum &＃61; 0;

&＃64;SuppressWarnings("null")public GetData(String pathname, List lines) throwsIOException{//读文件准备

File file &＃61; newFile(pathname);

InputStreamReader rdr&＃61; new InputStreamReader(newFileInputStream(file));

BufferedReader br&＃61; newBufferedReader(rdr);try{

String content&＃61;null;while((content&＃61;br.readLine())!&＃61;null) {

linenum&＃43;&＃43;;

Line newline&＃61; newLine();

List line &＃61; new ArrayList();

String[] station_single&＃61; content.split(" ");

String linename&＃61; station_single[0];//第一个元素为线路名

for(int i&＃61;1;i

if(i&＃61;&＃61;station_single.length-1 && station_single[i].equals(station_single[1]))//处理环线

continue;

line.add(station_single[i]);

}

newline.setName(linename);

newline.setStations(line);

lines.add(newline);

}

br.close();

}catch(IOException e) {

e.printStackTrace();

}finally{if (br &＃61;&＃61; null)try{

br.close();

}catch(IOException e) {

e.printStackTrace();

}

}

}

}

2.Floyd算法求最短路径

public classResult {private static final int max &＃61; 999999;private int[][] ShortestPath;private int[][] ShortestDis;public Result(int[][] G) {this.ShortestPath &＃61; new int[G.length][G.length];this.ShortestDis &＃61; new int[G.length][G.length];for(int i&＃61;0;i

}

}//Floyd核心算法

for(int k&＃61;0;kthis.ShortestDis[i][k]&＃43;this.ShortestDis[k][j]) {this.ShortestDis[i][j]&＃61;this.ShortestDis[i][k]&＃43;this.ShortestDis[k][j];this.ShortestPath[i][j]&＃61;this.ShortestPath[i][k];

}

}

}

}

3.初始化整个地图

public Map(List stations) {//初始化整个地图

this.stations &＃61;stations;this.subwayline &＃61; new int[stations.size()][stations.size()];this.path &＃61; new int[stations.size()][stations.size()];for(int i&＃61;0;i

subwayline[i][j]&＃61; 999999;

subwayline[j][i]&＃61; 999999;

}

}

}

4.主页面显示功能与北京地铁线路背景图

public class FrmMain extends JFrame implementsActionListener{private static final long serialVersionUID &＃61; 1L;private JMenuBar menubar&＃61;newJMenuBar();private JPanel statusBar &＃61; newJPanel();private JMenu menu_Manager&＃61;new JMenu("功能");

JFrame jf&＃61;newJFrame();private JMenuItem menuItem_Line&＃61;new JMenuItem("查询线路");private JMenuItem menuItem_ShortestPath&＃61;new JMenuItem("查询最短路径");private static List lines &＃61; new ArrayList<>();//存储.txt中的所有数据

private List stations &＃61; new ArrayList();//存储所有站点

public FrmMain() throwsIOException {//读文件

String filepath &＃61; "E:\\Software Engineering\\data.txt";

GetData data&＃61; newGetData(filepath,lines);//北京地铁图片

JLabel jl3&＃61;new JLabel(new ImageIcon("E:\\Software Engineering\\subway.jpg"));

jf.add(jl3);

jl3.setBounds(0, 100, 80, 60);

jf.pack();

jf.setVisible(true);this.setTitle("北京地铁小助手");

menu_Manager.add(menuItem_Line);

menuItem_Line.addActionListener(this);

menu_Manager.add(menuItem_ShortestPath);

menuItem_ShortestPath.addActionListener(this);

menubar.add(menu_Manager);

statusBar.setLayout(newFlowLayout(FlowLayout.LEFT));

JLabel label&＃61;new JLabel("欢迎使用北京地铁小助手^^");

statusBar.add(label);this.getContentPane().add(statusBar,BorderLayout.SOUTH);this.addWindowListener(newWindowAdapter(){public voidwindowClosing(WindowEvent e){

System.exit(0);

}

});this.setVisible(true);this.setJMenuBar(menubar);

}public voidactionPerformed(ActionEvent e) {if(e.getSource()&＃61;&＃61;this.menuItem_Line){

FrmLine dlg&＃61;new FrmLine(this,"查询线路",true,lines);

dlg.setVisible(true);

}else if(e.getSource()&＃61;&＃61;this.menuItem_ShortestPath){

FrmShortestPath dlg&＃61;new FrmShortestPath(this,"查询最短路径",true,lines,stations);

dlg.setVisible(true);

}

}

5.在查询页面处理最短路径

public class FrmShortestPath extends JDialog implementsActionListener{private List lines2 &＃61; new ArrayList<>();//存储.txt中的所有数据

privateResult result;privateMap map;private List list1 &＃61; new ArrayList<>(); //存储经过单个站点的地铁线的名字&＃xff0c;以列表储存

private List> lists &＃61; new ArrayList<>(); //存储经过所有站点的地铁线的名字&＃xff0c;将list1依次添加进lists中

private List passStation &＃61; new ArrayList<>(); //储存经过站点在数组中的下标

private JPanel toolBar &＃61; newJPanel();private JPanel workPane &＃61; newJPanel();private Button btnOk &＃61; new Button("查询");private JTextField edtStart &＃61; new JTextField(20);private JTextField edtEnd &＃61; new JTextField(20);private JLabel labelStart &＃61; new JLabel("起点:");private JLabel labelEnd &＃61; new JLabel("终点:");private JLabel labelTip &＃61; new JLabel("请输入您要查询的起点和终点^^");public FrmShortestPath(FrmMain frmMain, String s, boolean b, List lines, Liststations) {super(frmMain,s,b);

lines2.addAll(lines);

toolBar.setLayout(newFlowLayout(FlowLayout.RIGHT));

toolBar.add(btnOk);this.getContentPane().add(toolBar, BorderLayout.SOUTH);

workPane.add(labelStart);

workPane.add(edtStart);

workPane.add(labelEnd);

workPane.add(edtEnd);

workPane.add(labelTip);this.getContentPane().add(workPane, BorderLayout.CENTER);this.setSize(280, 150);double width &＃61;Toolkit.getDefaultToolkit().getScreenSize().getWidth();double height &＃61;Toolkit.getDefaultToolkit().getScreenSize().getHeight();this.setLocation((int) (width - this.getWidth()) / 2,

(int) (height - this.getHeight()) / 2);this.validate();this.btnOk.addActionListener(this);this.addWindowListener(newWindowAdapter() {public voidwindowClosing(WindowEvent e) {//System.exit(0);

}

});//把所有站点加入stations中

for(int i&＃61;0;i

stations.addAll(lines.get(i).getStations());

}

map&＃61; new Map(stations);//此map非彼map//初始化各个站点间的距离为1

for(int i&＃61;0;i

map.initDis(lines.get(i).getStations().get(j), lines.get(i).getStations().get(j&＃43;1));

}

}//求最短路径

result &＃61; newResult(map.getSubwayline());

}

&＃64;Overridepublic voidactionPerformed(ActionEvent e) {if(e.getSource()&＃61;&＃61;this.btnOk) {int flag1&＃61;-1;int flag2&＃61;-1;

String start&＃61; this.edtStart.getText();

String end&＃61; this.edtEnd.getText();

flag1&＃61;FrmMain.isStation(start);

flag2&＃61;FrmMain.isStation(end);if(start&＃61;&＃61;null || start.equals("") || end&＃61;&＃61;null || end.equals(""))try{throw newException();

}catch(Exception e1) {

JOptionPane.showMessageDialog(null, "起点/终点不能为空&＃xff01;","错误",JOptionPane.ERROR_MESSAGE);return;

}else if(flag1<0 || flag2<0){try{throw newException();

}catch(Exception e1) {

JOptionPane.showMessageDialog(null, "起点/终点不存在&＃xff01;","错误",JOptionPane.ERROR_MESSAGE);return;

}

}else if(start.equals(end)) {try{throw newException();

}catch(Exception e1) {

JOptionPane.showMessageDialog(null, "起点和终点不能相同&＃xff01;","错误",JOptionPane.ERROR_MESSAGE);return;

}

}else{//查询shortest path

int i &＃61;map.getIndex(start);int j &＃61;map.getIndex(end);int shortest &＃61; result.getMinDis(i,j);//需修改

if(shortest &＃61;&＃61; 999999) {try{throw newException();

}catch(Exception e1) {

JOptionPane.showMessageDialog(null, "两站点不可达&＃xff01;","错误",JOptionPane.ERROR_MESSAGE);return;

}

}

shortest&＃43;&＃43;;

String path&＃61; start&＃43;"到"&＃43;end&＃43;"需经过"&＃43;shortest&＃43;"个站\n";

passStation&＃61; result.indexToList(i,j);//存储最短路径

for(int k&＃61;0;k

List list &＃61; new ArrayList<>();

path&＃43;&＃61;(map.getName(passStation.get(k))&＃43;"(");//System.out.println(path);

for(Line l:lines2) {int flag&＃61;0;for(String name:l.getStations()) {

System.out.println(map.getName(passStation.get(i)));if(map.getName(passStation.get(i)).equals(name)){

path&＃43;&＃61;(l.getName()&＃43;" ");

list.add(l.getName());if(!list1.contains(name)) {

list1.add(name);

flag&＃61;1;

}

}

}if(flag&＃61;&＃61;1) lists.add(list);

}

}

path&＃43;&＃61;")";

path&＃43;&＃61;"\n";//存储换乘车站

List transfer &＃61; new ArrayList<>();for(int p&＃61;2;p

flag&＃61;1;break;

}

}if(flag&＃61;&＃61;0) {if(!transfer.contains(list1.get(p-1))); transfer.add(list1.get(p-1));

}

}

path&＃43;&＃61;"\n";

path&＃43;&＃61;"需要换乘"&＃43;transfer.size()&＃43;"次&＃xff1a;";for(int a&＃61;0;a

path&＃43;&＃61;(transfer.get(a)&＃43;" ");

}

path&＃43;&＃61;"\n";

FrmShowShortestPath dlg&＃61;new FrmShowShortestPath(this,"最短路径详情",true,path);

dlg.setVisible(true);

}

}

}

}

六、测试用例

1.主界面

包括功能与北京地铁线路背景图

2.查询线路

3.查询线路·输入为空

4.查询线路·输入不存在的线路

5.查询最短路径·同线路

6.查询最短路径·远站需换乘

7.查询最短路径·起点/终点为空

8.查询最短路径·输入站点不存在

9.查询最短路径·起点终点相同

七、总结

1.在上一次的需求分析中原本打算用Dijstra算法&＃xff0c;但是在写代码的过程中发现了Floyd算法更易实现&＃xff0c;于是就果断跑路Floyd算法了&＃xff0c;究其原因应该是需求分析不够深入&＃xff0c;没有进一步结合代码实现来思考。

2.写代码的过程中&＃xff0c;意识到多个UI界面弹窗之间传参数的麻烦之处&＃xff0c;经过这一次的锻炼&＃xff0c;对JAVA类与类之间传参数有了更好的理解。

3.认识到自己对JAVA还有许多不了解的“简便方法”&＃xff0c;在本次写博客的过程中在CSDN中获益匪浅&＃xff0c;希望以后也是多多锻炼&＃xff0c;继续在CSND和Baidu中学习更多的知识。

4.至于前端UI&＃xff0c;我还是以较为“偷懒”的方式用了在暑假短学期学到的JAVA Swing&＃xff0c;算是对之前学习内容的一个复习与巩固叭。

5.算是第一次写这么完整的技术博客&＃xff0c;也是一次不可多得的实战经验呢^^