Note: you may implement either the proposed solution or any modification you develop. You are not required to implement a modified proposal if you do not wish to do so. In each case explain your answer and, if necessary explain how you might modify the proposed algorithm to address any issues you identify. Programs must compile and run under g++ (C++ programs) Programs which do not compile and run will receive no marks. Programs should be appropriately documented with comments.

Program should be implemented in single .cpp file. All coding must be your own work. Standard libraries of data structures and algorithms such as STL may not be used, nor may code be sourced from textbooks, the internet, etc. Standard libraries of data structure and algorithm such as STL may not be used. A program which produces the correct output, no matter how inefficient the code, will receive a minimum of 50% of the mark for the program. Additional marks beyond this will be awarded for the appropriateness, i.e. efficiency for this problem, of the algorithms and data structures you use. Programs which lack clarity, both in code and comments, will lose marks.

Submission: Assignments should be typed into a single text file called ass1.ext where ext is the appropriate file extension. A pdf file describing your solution should also be produced. This file should contain at least: The documentation for your program - A high-level description of the overall solution strategy chosen for the shortest path problem. A high-level description of the design and overall solution strategy you have developed for the second shortest path problem. A list of all of the data structures used, where they are used and the reasons for their choice. A list of any algorithms used, where they are used and why they are used. The answers, explanations and possible changes for each question in the questions section.