Computing BSc Network Routing Design Project: Dijkstra's Algorithm

This project requires the design and implementation of a network routing system, initially as a command-line application and subsequently with a GUI, to model and simulate shortest path design based on Dijkstra's algorithm. The project involves reading network data from a file, calculating the shortest paths, and outputting the results to the VDU and a file. The GUI version, built using TkInter, is to graphically display the graph, highlight the calculated shortest path, offer file saving, and allow for the graphical creation of routes by adding nodes and lines. The project emphasizes object-oriented programming principles, design documentation, and user interface design, with assessment based on the quality of the design, implementation, and documentation. Students are expected to demonstrate a strong understanding of Dijkstra's algorithm and its application in network routing, including the use of appropriate data structures and algorithms to efficiently solve the shortest-path problem. The project covers both the theoretical aspects of algorithm design and the practical aspects of software development, with a focus on delivering a user-friendly and functional application.

Division of Applied Sciences, Computing & Engineering
Computing BSc Programmes
Task A:
You are create a program design to support your companies design of network routing
design. This will initially be at the command line to prove the concept and then extended.
Your organisation needs to model and simulate its shortest path design based on the
Dijkstra’s shortest path algorithm
Shortest-paths is a broadly useful problem-solving model
• Maps
• Robot navigation.
• Texture mapping.
• Typesetting in TeX.
• Urban traffic planning.
• Optimal pipelining of VLSI chip.
• Subroutine in advanced algorithms.
• Telemarketer operator scheduling.
• Routing of telecommunications messages.
• Approximating piecewise linear functions.
• Network routing protocols (OSPF, BGP, RIP).
• Exploiting arbitrage opportunities in currency exchange.
• Optimal truck routing through given traffic congestion pattern.
Code for this problem is to be created in Python using the command line for proof of
concept and to be based on a file to be provided (See guidance ).
1. Open the file and read on the data into suitable data structure.
2. Perform the shortest path calculation.
3. Output the results to the VDU.
4. Save the results to a file.
1

Task B.
Your algorithm has proven to be successful and a GUI version is urgently required by the
network team. You are therefore requested to create a GUI version of the original design
with the following demands
1. Input from a data file
2, Graphical display of the graph.
3. The calculated shortest path to be highlighted
4. A save file option
5. The ability to create a route graphically adding nodes and lines using the mouse.
Guidance:
Your tutor will act as the Network specialist, will be available for interview during class / lab
sessions.
A router diagram will be provided.
You may solve the shortest path by simple (manual calculation) but for a more advance
approach you will implement the Dijkstra algorithm to demonstrate a deeper understanding
of the issue.
Further guidance:
You are to use TkInter for the GUI development
The design of a realistic and easy-to-understand user interface is expected.
Your solution should include classes, methods and event/general functions as appropriate.
Refer to the Assessment criteria below for guidance on how to pass this assignment. Your
work will be assessed on how you define / model the requirements in your design
documentation and how you communicate your design decisions. You may obtain further
guidance from the module tutor.
Submission: (All submissions are through the relevant assessment Moodle on Moodle)
• A full report containing your design documentation
2

• Testing and debugging
• Demonstrate your GUI solution.
Assessment:
To obtain a ‘C’ all the criteria listed must be achieved. Higher grades will be given for work
of higher quality. For example a ‘B’ – ‘B+’ for work of high quality in some areas and a ‘A’
for work of high quality in all or most areas.
Learning Outcomes Assessment Criteria
To achieve each outcome a student must demonstrate
the ability to:
Implement program
designs in an object-
oriented programming
language.
 Investigate software design methodologies and
practices to produce appropriate analysis, design,
requirement and user documentation
Quality will be demonstrated by the following:
1. Creativity and adaptability
2. Showing synthesis of concepts
3. Breadth and depth of the solution design
4. Autonomy and independence
5. Coherence of design
6. Extent of exploitation of the GUI
3

A grade
A will be awarded for a detailed report of professional standard
• Very high standard of implementation
• Excellent understanding of good programming practice
• Clearly structured and logically developed algorithms
• Good use of data structures
A Grade B+
will be awarded for an interesting report, demonstrating clear insight and motivated
research.
• A good standard of implementation
• Clearly structured and logically developed arguments
• Some evidence of independent research
• Some evaluation and synthesis of source material
• Relevant data and examples, all properly referenced
A grade B will be awarded for a good report, demonstrating insight
and research. • Attempts analysis but includes some errors and/or
omissions
• Shows awareness of issues but no more than to be expected from attendance at classes •
Arguments reasonably clear but underdeveloped
• Insufficient evidence of independent research
• Insufficient evaluation of source material
• Some good use of relevant data and examples, but incompletely referenced
A grade C will be awarded for a useful overview of
the subject.
• Weak understanding
• Shows some awareness of techniques but also some confusion
• No evidence of independent implementation
• Reliance on a replication of class notes
• Superficial use of data structures
Refer: Work in respect of which the student is referred.
• No understanding evidenced, No grasp of implementation and many errors and omissions
4

Finding the best path
5

6