computer science

2025-05-08 Admin 写评论

Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

Assignment 4 (Due, Wednesday April-30-2025)

(40/100 points for assignments)
Twin-towers are common building style in largest cities such as Shenzhen. Figure 1 shows the pictures of the Xinghe twin Towers in Shenzhen.

The objective of this assignment is to implement functions of

1) Constructing a graph of a twin tower automatically (see Figure 2 and 3), and

2) Finding a shortest path between two offices in the Towers, e.g. from room A125 to room B923.


Figure 1. The twin-tower of Xinghe in Shenzhen.

Figure 2 shows the plane for the ground floor. There are 88 nodes in total at the ground floor, of which 4 nodes are used to connect Tower A and Tower B, and the elevators at both ends of the building as well. Other 84 nodes are used to connect office rooms and corridors.

Node definitions

Node numbers for office room: Office rooms are numbering in a format of name of Tower (A/B) , followed by floor number (1-n), and then by room number (1-28). The first letter is the name of the Tower (A or B), while the last two digits are the room number(01-28), any number in between is the floor number(1-n). For example A120 is room Nr. 20 at the first floor of Tower A, or B10025 is room Nr. 25 at the 100 th floor of Tower B.

Node numbers for corridors: Nodes in corridors are defined in a similar format: name of Tower (A/B) followed by the letter C (for Corridors), then by floor number (1-n) and then the corridor node number (1-14) from left to right. For example AC1109, is the 9 th corridor node from left at the 11 th floor of A tower.

Node numbers for elevators: Nodes for both elevators are defined in a similar format: name of Tower (A/B) followed by the letter E (for Elevators), then by floornumber (1-n) and then elevator node number (1-2) from left to right. For example BE1101, is the elevator on the left side at the 11 th floor of B tower.

Figure 2. The plane for the ground floor.
Figure 3 shows the planes for the floors 2 nd - n th . The connections between two towers are only available at the ground floor. There is no connection between Tower A and B at other floors.

Figure 3. Floor planes for the 2 nd - n th floors. Node numbers are shown for 2 nd floor only. For other floors, please use the format mentioned above to define the node numbers.

Edge definitions

1) Nodes are connected as shown in Figures 2 and 3. It is an undirected graph, means all arcs are bidirectionally connected.

2) The weights for arcs connecting Tower A and B are 100. This is only for the two bi-directional arcs at the ground floor.

3) The weights for arcs connecting two elevator nodes between two neighbor floors are variables as input parameters (see explanation later in the function). Arcs connecting two elevator nodes across only one floor. For example, in case to travel for 10 floors, it will travel floor by floor. This will make the assignment simple.
4) The weights for arcs connecting an elevator node and a corridor nodes is 8.
5) The weights for other arcs are 5.
6) For every 10 th floors ( e.g. 10 th , 20 th , 40 th , ...) in Tower A, there is a two-way crossbeam between A(n)22 - B(n-1)08 (e.g. from A1022 - B908, A2022-B1908), and another two-way crossbeam between A(n)23-B(n+1)09 (e.g. A1023-B1109, A2023-B2109,...). The weights of the crossbeams are the same as the elevator AE101.

Submissions

You need to develop the following function using the Dijkstra algorithm. int FindShortestPath(std::string start, std::string end,
std::vector<std::string>& path,int** eWeights);
Input:

start - is name of the starting point.

end - is the name of the end point. eWeights - is a 4xm matrix that contains the weights of the outward arcs for the elevator nodes for each floor. m is the number of floors. The first row of the matrix eWeights[0][n-1] contains the weights of the outwards arcs for the elevator AEn1, n is the floor number, while the second row of eWeights[1][n-1] is for AEn2, the third row of eWeights[2][n-1] is for BEn1, and eWeights[3][n-1] is for BEn2. The weights for elevator nodes might be very large at a particular floor of a particular elevator, so that it is possible to find the shortest path via e.g. the crossbeams.

Output

The return value is the distance of the whole path (sum of all arcs in the path)

std::vector<std::string>& path is a vector of string, holds the names of the nodes of the path in order starting from the starting node.

Hints: The input strings “start” and “end” includes the information about the floor numbers in each Tower. You should utilize it to create your graph.Submission:

Please submit: The source codes in a single file or one header file (*.h) + one source file (*.cpp). NO OTHER DOCUMENTS IS NEEDED.

Your score for this assignment is based on two parts:

1) Basic functionality (50%). Criteria: Your function can provide correct answers within 30 seconds.
2) Performance (50%). It is based on performance ranking.
- Top 20%, full points, 50/50
- 21%-50%, 40/50;
-51%-75%, 30/50;
Others
20/50

发表评论

电子邮件地址不会被公开。 必填项已用*标注