Shortest-Path代做、代写Java程序语言、代做Java、代写algorithm留学生

日期：2019-04-03 10:01

Coursework on the Shortest-Path Problem

It is worth 13 marks.

Task List

For this coursework, you need to design and implement a Java program that solves the following

two shortest-path problems given a graph G, AND provide a short description on your

implemented algorithm and its complexity analysis (MUST be less than 2 pages, Font

12.).

Task 1: Given a selected starting node, find the shortest path from the selected node to every

other node.

Task 2: Among all the nodes, choose the one with the smallest summation of shortest distances

to all other nodes. E.g. The shortest distances of Node 0 to all other nodes are: d0,1, d0,2, ..., d0,n,

then the summation for Node 0 is: d0=d0,1+d0,2+...+d0,n. You should find the node with smallest

summation, e.g. imin = argmin di.

Problem Description

We may often encounter many shortest path problems in life, e.g., to find the optimal driving

path from one place to another across the city; to route a packet through the internet from your

PC to the server. In this coursework, we will practice how to find the optimal path from one city

to another given a graph. An example graph (map) is shown in Fig. 1.

10 cities from China are chosen and they are interconnected by road. Cities are indexed with a

number from 0 to 9, e.g. Beijing’s index is 0 and Dalian’s index is 9. The distance from one city

to another is shown on the edges.

Fig. 1: An example graph that interconnects 10 cities in China. The nodes represent the cities and

the edges represent the distance between two cities.

Task Description and Guidelines

Task 1: Given a selected starting node, find the shortest-path from the selected node to all

other nodes.

Objectives: This is to simulate that when there is one logistic center (the selected starting city),

how far the other cities are apart from this city. This is a standard single-source shortest path

problem.

Selecting Starting City: Use your student ID to select the starting city, e.g. If your student ID is

6543210, the last digit 0 is chosen. So the starting city is Beijing (index 0).

Output: You should write the following into a file named “Task1Result.txt”. For example, if

your source city is Beijing:

[Student Name],[Student ID]

Source City:Beijing

To Tianjin:125km,Beijing,Tianjin.

To Chengde:226km,Beijing,Chengde.

...

To Dalian:916km,Beijing,Tianjin,Dalian.

The sum of the shortest distances:****km

The first line is your name and your student ID, separated by ‘,’.

The second line is your source city.

The third to eleventh lines are the shortest distances from your source city to the destination

cities, and the optimal/shortest paths.

The last line is the sum of all the shortest distances.

Task 2: Among all the nodes, choose the one with the smallest summation of distances to all

other nodes. E.g. The shortest distance of Node 0 to all other nodes are: d0,1, d0,2, ..., d0,n, then the

summation for Node 0 is: d0=d0,1+d0,2+...+d0,n. You should find the node with smallest

summation, e.g. imin = argmin di.

Objectives: This is to find the city with the shortest summation of distances to other cities. This

city will be a good choice for logistic center.

NOTE: Remove the city you used as the starting city in Task 1, e.g. If your student ID is

6543210, then in Task 1 the starting city is Beijing, and you should remove Beijing from the

graph and its associated edges for Task 2. For the remaining 9 cities, find the one with the

smallest summation of distances to other cities.

Output: You should write the following into a file named “Task2Result.txt”.

[Student Name],[Student ID]

[City 0],[SummationOfDistanceToCity0]

...

[City 9],[SummationOfDistanceToCity9]

The chosen logistic center is [City Name]. Summation of distances is: ****km.

The first line is student name and student ID.

The second to tenth lines are: the name of remaining 9 cities, and its summation of distances to

all cities.

The 11th line is: the chosen logistic center and its summation of distances to all cities.

Requirements

You may design your own algorithm to solve this problem, but your algorithm MUST obtain

the globally optimal solution.

You MUST implement your solution in Java.

Your program should load the graph from a text file. You may define your own format for the

text file. You may use adjacency matrix, adjacency list, adjacency map or edge list to

implement the graph.

How to submit

You should zip all the java files, your text file for the graph, the result files and the PDF file for

the explanation of your algorithm and its complexity analysis in ONE zipped file.