Singapore is Connected with SMRT Stations to Facilitate Quicker Transportation: Python Assignment, SMU, Singapore

Intended Learning Outcomes

1. Understand and select appropriate algorithms for solving a range of problems
2. Design and implement algorithms and data structures for novel problems.
3. Reason about the complexity and efficiency of algorithms
4. Demonstrate the use of advanced language features such as events, GUIs and concurrency

SMRT Smart Mapper (SSM)

Singapore is connected with SMRT stations to facilitate quicker transportation. SSM is an application where the stations are linked up. The diagram in the Appendix shows the map of the SMRT system connected.

Design your SSM application using a WEIGHTED GRAPH.

Requirements for SSM

The requirements are listed below. You should have been completing these requirements on a weekly basis.

Note that marks are also awarded for presentation.

Requirement 1 – REPRESENTATION of the map in Figure 1 (Appendix A)

Represent the network of the SMRT stations shown in Figure 1 with a weighted graph using adjacency list or linked-list.

Requirement 2 – Link an SMRT station to another SMRT station. Add a link between two stations on the map.

Requirement 3 – Delink an SMRT station from an SMRT station.

Remove a link between two stations on the map. If this is the last link on the map, prompt the user that the link cannot be removed.

Requirement 4 – Traverse the SSM Map from a given SMRT station.

Hint: This requirement can be done using a Bread-First Search or a Depth First search.

Requirement 5 – Perform Dijkstra’s Shortest Path Algorithm given a source station and a destination station.

Print the path and all possible shortest paths from source to destination and state the weight (1 link is considered the weight of 1).

Requirement 6 – Build a GUI that will allow the user to perform the actions listed in Requirements 1 to 5.

APPENDIX A

FIGURE 1 – SMRT MAP