A formal proposal for a MSc project that will be submitted in partial fulfillment of a University of Greenwich Masters Degree

Using Floyd Warshall algorithm to navigate a theme park

Topic Area: Algorithms and Data Structures

Keywords associated with the project: Graph Algorithms, All-Pairs Shortest Paths, FloydWarshall algorithm, Python, Graph Theory

MSc Modules studied that contribute towards this project: You need to type in a minimum of two modules here.

1. Overview

The use of computers in everyday life is expanding these days. Everything is becoming more computerized. While this innovation is at its apex, most widely used applications utilize graph theory in some form, such as search engines, which are mostly based on graphs. Because of the extensive research done in graph theory, it has grown to be a very broad field in mathematics. Comprehension in real-world applications requires a thorough understanding of the numerous graphs presented in graph theory.

Facebook's Graph API is likely the greatest example of graph application to real-world problems. The Graph API represents a paradigm shift in large-scale data providing. Everything on The Graph API is a vertice or a node. A vertice is something that has data-storage qualities. And every link or relationship provides an advantage. This might include a User publishing a Photo, Video, or Comment, a User updating their profile with their place of birth, a User upgrading their relationship status, a User like a Friend's Photo, and so on.

Another common real-world application of the graph algorithms is path optimizations.

Path optimizations are generally concerned with locating the optimum link that meets some preset criteria, such as speed, safety, fuel, and so on, or a group of criteria, such as products and routes. In real life, it can assist in determining the quickest route to take in order to go from one area to another in the fewest amount of time. In this case, the locations serve as vertices, and the time necessary to go by various routes equals the weight assigned to that route or edge.

So, in this project, I intend to implement and modify the FloydWarshall algorithm for finding the All-Pairs Shortest Path. I want to utilize it as a guide at one of the most popular sites where we tend to get lost and wish we had a guide, a theme park. This algorithm can assist its users in finding and reaching their destination with least possible effort.

2. Objectives

2.1 To study the Floyd-Warshall algorithm in depth and reflect upon its usefulness and applications in real life.

• By reading books, journals, reputed research papers, online websites and brain storming the real-life use cases.
• A Report

2.2 To modify the Floyd-Warshall algorithm to reconstruct the shortest path and not just the shortest distances between all nodes.

• By implementing the code and inspecting what changes are required to make it churn shortest path in addition to minimum distances.
• A Python file (.py extension) containing the modified algorithm for generating shortest path.

2.3 To develop a shortest path finding application between any two specified points based on Floyd-Warshall algorithm for a theme park.

• By designing the use case, robustness diagram, model required and investigating all the elements involved and then combining them to make a scenario and implement the algorithm to achieve the objective as specified.
• A zipped project file containing my theme park implementation project source code in Python.

2.4 To investigate the current efficiency of the Floyd-Warshall algorithm and to devise measures to increase the current efficiency in order to address even larger datasets.

• By reading books, journals, reputed research papers and then running test on larger datasets and investigating results in detail.
• A report.

How the objectives will be achieved

• By reading books, journals, reputed research papers, online websites and brain storming the real-life use cases.

• By implementing the code and inspecting what changes are required to make it churn shortest path in addition to minimum distances.

• By designing the use case, robustness diagram, model required and investigating all the elements involved and then combining them to make a scenario and implement the algorithm to achieve the objective as specified.

• By reading books, journals, reputed research papers and then running test on larger datasets and investigating results in detail.

Deliverables include:

• A detailed report on my findings for my objectives 1 and 4.

• A Python file (.py extension) containing the modified algorithm for generating shortest path.

• A zipped project file containing my theme park implementation project source code in Python.

These are the time estimates for each mentioned objective:

• First objective will take around 15 days as I will need to go through sufficient materials in order to make qualified research.

• Second objective will take around 3 days as I will need to study the current version of the code and then try to modify it to achieve my objective.

• Third objective will take the most of my time and I guess it be around 20-30 days because of the nature of the work which is about developing a full-fledged real-world application with presentable user interface.

• Fourth objective will be completed as I go through my first objective as they both require to gain knowledge by reading available quality material on the topic.

3. Legal, Social and Ethical Issues

I assure that all of the work presented in this project will either be my own or properly attributed and referenced if borrowed from somewhere else. I will also make sure to borrow only the work with proper sharing license or permissions.

I do not think this work will be offensive to anyone as my work does not include any racial, social, or any such aspect as to create conflicts among people. I will also not be involving any real-world people in either form nor real world theme park.

Also, having said all that, I will take utmost care that the final deliverables consider the legal, social and ethnic aspects also and do not hurt sentiments of any type of community.

4. Resources

Resources required for this task are:

• Access to journals and research papers.
• Access to required books.

Softwares include:

• Visual Studio Code
• PyCharm
• Notepad

5. Critical success factors

• Critical success factors include easy access to aforementioned resources and their quality which is also crucial in attaining my objectives.

• Risks also include to be able to modify and improve the current standard algorithm.

• Other than that, one more risk is failing to develop the application which operates and is applicable in real life also.

Risk Treatment and Mitigation:

• In case of difficult access to required resources, I will fall back to using open source and free alternates of the required resources.

• Also, in case of not being able to improve current algorithm, I plan to study more advanced algorithms to see if any aspect of those algorithms can be used to achieve my objective.

• As for the risk about theme park navigation application, I will start with small dataset and break my development into many small parts and set milestones for those, thus gradually building a full-fledged working application.

6. Schedule

These are the time estimates for each mentioned objective:

• First objective will take around 15 days as I will need to go through sufficient materials in order to make qualified research.

• Second objective will take around 3 days as I will need to study the current version of the code and then try to modify it to achieve my objective.

• Third objective will take the most of my time and I guess it be around 20-30 days because of the nature of the work which is about developing a full-fledged real-world application with presentable user interface.

• Fourth objective will be completed as I go through my first objective as they both require to gain knowledge by reading available quality material on the topic.

7. References

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C., 2022.Introduction to algorithms. MIT press.

• This will help in gaining basic knowledge and strengthening my foundations.

Hougardy, S., 2010. The FloydWarshall algorithm on graphs with negative cycles.Information Processing Letters,110(8-9), pp.279-281.

• This will help me gaining even more conceptual knowledge on the topic.

Mirino, A.E., 2017, October. Best routes selection using Dijkstra and Floyd-Warshall algorithm. In2017 11th International Conference on Information & Communication Technology and System (ICTS)(pp. 155-158). IEEE.

• This will help me modify and improve the current algorithm to select shortest routes.

Appendix A