【实验】Dijkstra算法解决欧洲旅行问题
说明
这题挺好的，建议自己思考思考，独立完成……
这下面的代码写的一般般，如果自己有能力，大可不必参考。
Experiment 4 Europe by Rail（4 hours）
Prerequisites: Students should have mastered the following prerequisite skills.
- Graphs - Knowledge of graph representation, particularly adjacency lists
- Graph Algorithms - Knowledge of Dijkstra’s shortest path algorithm
Goals: This assignment is designed to reinforce the student’s understanding of the implementation of a fundamental graph algorithm
Outcomes: Students successfully completing this assignment would master the following outcomes.
- Understand graph representation
- Understand how to implement Dijkstra’s shortest path algorithm
Background
Traveling through Europe by rail is a cheap and effective way to experience the sights, sounds, and culture of a wide array of countries and cities. Generally, travelers purchase rail passes that allow unlimited travel on the rail system. Individual tickets, however, can be purchased.
Description
The program for this assessment calculates the cheapest route between two cities in a mock European rail system. The graph that represents the rail system is pictured below.
&sbnp;&sbnp;&sbnp;&sbnp;In this program, a weighted graph is constructed to represent rail services to and from European cities. Each service from a city has an associated destination city, a fee (in Euros), and a distance (in kilometers). The program processes user input of a source city and a destination city. The program then displays the cheapest route from the source city to the destination city. In addition, for each route, the total cost and total distance are displayed. The file services.txt contains the data for the available services.
Classes
This program should utilize three main classes, class City, class Service, and class RailSystem. Class City maintains information about a city. Class Service models a rail service from the rail system. This class contains public data members for a destination city, a fee, and a distance. Both of these classes are used by class RailSystem.
Figure 1 A mock European rail system
Class RailSystem models the rail system using an adjacency list representation. The following image represents how a portion of the rail system is represented. Note that the ticket fees and distances are left out to simplify the picture.
Figure 2 Adjacency list representation of the rail system
Essentially, in the above representation, a linked list of outgoing services can be indexed using a string containing the source city name. For example, notice in the above picture, Madrid has three outgoing services: one to Lisbon, one to Bern, and one to Paris. This matches the picture of the rail system at the top of this handout.
Sample output from this program is shown in the figure below.
Figure 3 Output from a sample solution
The algorithm to be used is a positive-weighted, shortest path algorithm. Each City is a node in a graph, and each Service is an edge. Edges have an associated cost: the fee for the ticket. The goal is to find the cheapest route from the source city to the destination city.
To perform a new search, a reference to a Service object representing the start city should be added to an initially empty candidates queue. The algorithm continues by exploring the services of each candidate city, possibly adding new candidates to the list. The algorithm labels each City object with a number representing the cost of the cheapest route to it from the origin found so far. This can be stored in member total_fee of class City. This value may decrease as new routes that are cheaper are found, but the value never increases.
To recover the actual path found by the search, every City object contains a string from_city. This string will be updated by the search algorithm to contain the name of the city by which it was reached through the cheapest path. In other words, if examining Brussels reveals a cheaper path to Paris, update variable total_fee of the City object that corresponds to Paris, and set its from_city equal to “Brussels”. Once the search is complete, the cheapest route to the destination has been found, and the from_city strings can be traversed from the destination to the origin to reconstruct the path.
Files
- services.txt - This file contains data that defines the rail system services.
Tasks
- To complete this assessment, you need to complete the implementation of a Graph data structure and the above mentioned classes.
- To begin, verify the file needed for this assessment. Following is an ordered list of steps that serves as a guide to completing this assessment. Work and test incrementally. Save often.
- Begin by completing the implementation of class City and Service.
- Next, writing the class RailSystem and complete the member function load_services. The data file of services is services.txt. Function load_services() must correctly store the cities and outgoing_services.
- Then, finish the implementation of function RailSystem::reset. This function should reset the data members of the City objects.
- Next, complete the definition of function calc_route(). It should use a positive-weighted, shortest path algorithm.
- Finally, implement function recover_route(). Function recover_route() accepts the name of a destination city as an argument, and returns a string which contains, in order, the city names from the source city from which the destination city was reached through the destination city. The path can be recovered through the from_city strings, which should have been set by function calc_route(). The city names must be separated by the four-character string " to ". See the screen shot of sample output above for samples of strings created by function recover_route().
Submission
Submit all the codes you need to complete.
数据文件
services.txt
Lisbon Madrid 75 450
Madrid Lisbon 55 450
Madrid Paris 100 1300
Madrid Bern 15 1500
Paris London 110 450
Paris Bern 35 600
Paris Vienna 75 1300
Paris Brussels 135 300
Paris Madrid 100 1300
London Paris 110 450
Rome Bern 75 900
Bern Rome 75 900
Bern Paris 15 600
Bern Sarajevo 25 1100
Bern Madrid 45 1500
Brussels Paris 225 300
Brussels Amsterdam 185 200
Brussels Berlin 65 800
Amsterdam Brussels 125 200
Amsterdam Copenhagen 45 800
Amsterdam Berlin 45 700
Copenhagen Amsterdam 45 800
Berlin Amsterdam 75 700
Berlin Brussels 35 800
Berlin Prague 45 350
Berlin Warsaw 35 900
Prague Berlin 55 350
Prague Vienna 45 300
Prague Warsaw 35 850
Warsaw Berlin 35 900
Warsaw Bucharest 25 1700
Warsaw Prague 25 850
Vienna Prague 45 300
Vienna Paris 75 1300
Vienna Budapest 45 300
Budapest Vienna 25 300
Budapest Bucharest 25 900
Budapest Sarajevo 15 600
Sarajevo Bern 25 1100
Sarajevo Sofia 15 600
Sarajevo Skopja 15 500
Sarajevo Budapest 25 600
Sofia Sarajevo 25 600
Sofia Skopja 15 200
Skopja Sofia 15 200
Skopja Tirane 15 200
Skopja Sarajevo 15 500
Tirane Athens 55 700
Tirane Skopja 35 200
Athens Tirane 55 700
Bucharest Budapest 25 900
Bucharest Warsaw 25 1700
Dublin Belfast 25 167
Belfast Dublin 25 167
Code
City类：
public class City {
private String name;
private String from_city;
private int total_fee;
private int total_distance;
private boolean visited;
private Service service;
public City(String name) {
this.name = name;
service = null;
visited = false;
}
public City(String name,String from_city,int total_fee,int total_distance,boolean visited,Service service){
this.name = name;
this.from_city = from_city;
this.total_fee = total_fee;
this.total_distance = total_distance;
this.visited = visited;
this.service = service;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getFrom_city() {
return from_city;
}
public void setFrom_city(String from_city) {
this.from_city = from_city;
}
public int getTotal_fee() {
return total_fee;
}
public void setTotal_fee(int total_fee) {
this.total_fee = total_fee;
}
public int getTotal_distance() {
return total_distance;
}
public void setTotal_distance(int total_distance) {
this.total_distance = total_distance;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public Service getService() {
return service;
}
public void setService(Service service) {
this.service = service;
}
@Override
public String toString() {
return "City [name=" + name + "]";
}
}
Service类：
public class Service {
private int distance;
private int weight;
private String start_city;
private String end_city;
private Service link = null;
public Service () {}
public Service(int d) {
this.distance = d;
}
public Service (String sc,String ec, int w, int d){
this.start_city = sc;
this.distance = d;
this.weight = w;
this.end_city = ec;
}
public String getStart_city() {
return start_city;
}
public void setStart_city(String start_city) {
this.start_city = start_city;
}
public String getEnd_city() {
return end_city;
}
public void setEnd_city(String end_city) {
this.end_city = end_city;
}
public int getDistance() {
return distance;
}
public void setDistance(int distance) {
this.distance = distance;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public Service getLink() {
return link;
}
public void setLink(Service link) {
this.link = link;
}
}
RailSystem类,注意filename的路径被我改了，并换了…表示部分路径，自行调整一下：
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Stack;
import java.util.StringTokenizer;
public class RailSystem {
private static Map<String, City> CITIES = new HashMap<>();
private final static int MAX_NUM_OF_VERTEXS = 30;
private static int NUM_OF_VERTEXS;
/**
* 得到顶点的数目
* @return
*/
public int getNumOfCity() {
return NUM_OF_VERTEXS;
}
/**
* 插入顶点
* @param c1
* @return
*/
public static City insertCity(String c1) {
if (NUM_OF_VERTEXS >= MAX_NUM_OF_VERTEXS)
return null;
NUM_OF_VERTEXS++;
City v = new City(c1);
CITIES.put(c1, v);
return v;
}
/**
* 插入边
* @param c1
* @param c2
* @param weight
* @param distance
*/
public static void insertEdge(String c1, String c2, int weight,int distance) {
Service vex1 = new Service(c1,c2,weight,distance);
if(!CITIES.containsKey(c1)) {
insertCity(c1);
CITIES.get(c1).setService(vex1);
}
// 索引为index1的顶点有邻接顶点
else if(CITIES.containsKey(c1)){
vex1.setLink(CITIES.get(c1).getService());
CITIES.get(c1).setService(vex1);
}
}
/**
* 加载文件，构建图
* @param address
* @throws IOException
*/
public static void load_services(String address) throws IOException {
String str = "";
StringTokenizer st;
FileInputStream fis = new FileInputStream(address);
InputStreamReader isr = new InputStreamReader(fis);
BufferedReader br = new BufferedReader(isr);
while ((str = br.readLine()) != null) {
st = new StringTokenizer(str, " ");
insertEdge(st.nextToken(),st.nextToken(),Integer.valueOf(st.nextToken()),
Integer.valueOf(st.nextToken()));
}
br.close();
isr.close();
fis.close();
}
/**
* 重新设计交通图
* @param address
* @throws IOException
*/
public void reset(String address) throws IOException {
CITIES.clear();
load_services(address);
}
/**
* Dijkstra算法得到最短路径
* @param name
*/
public static void calc_route(String name) {
if(!CITIES.containsKey(name)) {
System.out.println("不存在"+name+"城市！");
}
City begin_city = CITIES.get(name);
//初始化路程和费用
Iterator<String> iter = CITIES.keySet().iterator();
ArrayList<String> allcity = new ArrayList<String>();
while (iter.hasNext()) {
allcity.add(iter.next());
}
for (int i = 0; i < allcity.size(); i++) {
CITIES.get(allcity.get(i)).setTotal_fee(Integer.MAX_VALUE);
CITIES.get(allcity.get(i)).setFrom_city(name);
}
Service current = begin_city.getService();
while (current != null) {
CITIES.get(current.getEnd_city()).setTotal_distance(current.getDistance());
CITIES.get(current.getEnd_city()).setTotal_fee(current.getWeight());
current = current.getLink();
}
begin_city.setTotal_fee(0);
begin_city.setTotal_distance(0);
begin_city.setVisited(true);
// 处理从源点到其余顶点的最短路径
for (int j = 0; j < allcity.size(); j++) {
int min = Integer.MAX_VALUE;
int mind = Integer.MAX_VALUE;
String closest_city = null;
// 比较从源点到其余顶点的路径长度
for (int ji = 0; ji < allcity.size(); ji++) {
// 从源点到j顶点的最短路径还没有找到
if (CITIES.get(allcity.get(ji)).isVisited() == false &&
CITIES.get(allcity.get(ji)).getTotal_fee() < min) {
closest_city = CITIES.get(allcity.get(ji)).getName();
min = CITIES.get(allcity.get(ji)).getTotal_fee();
mind = CITIES.get(allcity.get(ji)).getTotal_distance();
}
}
// 找到源点到索引为index顶点的最短路径长度
if (closest_city != null) {
CITIES.get(closest_city).setVisited(true);
current = CITIES.get(closest_city).getService();
}
// 更新当前最短路径及距离
for (int jii = 0; jii < allcity.size(); jii++) {
while (current != null) {
if (!CITIES.get(current.getEnd_city()).isVisited() &&
(min + current.getWeight()) < CITIES.get(current.getEnd_city()).getTotal_fee()) {
CITIES.get(current.getEnd_city()).setTotal_fee(min + current.getWeight());
CITIES.get(current.getEnd_city()).setTotal_distance(mind + current.getDistance());
CITIES.get(current.getEnd_city()).setFrom_city(closest_city);
}
current = current.getLink();
}
}
}
}
/**
* 输出最便宜结果
* @param c1
* @param c2
*/
public static void recover_route(String c1,String c2) {
Stack<String> st = new Stack<String>();
st.push(c2);
int i = 1;
String cn = CITIES.get(c2).getFrom_city();
st.push(cn);
while(!cn.equals(c1)){
i++;
cn = CITIES.get(cn).getFrom_city();
st.push(cn);
}
String roote = st.pop();
for(int j = 0;j<i; j++) {
roote = roote + " to " + st.pop();
}
System.out.println(roote+"\n");
}
public static void main(String[] args) throws IOException {
load_services("src/com/.../structure/resources/services.txt");
System.out.println("Enter a start and destination city：<'quit' to exit>");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
StringTokenizer st;
while(!str.startsWith("quit")){
st = new StringTokenizer(str, " ");
String c1 = st.nextToken();
String c2 = st.nextToken();
calc_route(c1);
System.out.println("The cheapest route from " + c1 + " to " +c2+"\n");
System.out.println("costs "+ CITIES.get(c2).getTotal_fee() +" euros"+
" and spans " + CITIES.get(c2).getTotal_distance() +" kilometers"+"\n");
recover_route(c1,c2);
System.out.println("Enter a start and destination city：<'quit' to exit>");
str = br.readLine();
}
System.out.println("你输入了\"quit\"，程序已经退出！");
br.close();
}
}
算法优化
说实话这代码写的很low，而且Dijkstra算法可以用堆和优先队列进行优化的，不必如此麻烦。