SOURCE CODE INCLUDED
ABSTRACT
In the fundamental operation in computer science, Graph algorithm is a great tool used to solve problems related to graph theory and this algorithms have wide applications in solving routing problems. For the purpose of this project four algorithms from the many types of graph algorithms were selected which are Dijkstra’s, Bellman-Ford, kruskal and prim’s Algorithm and it application in solving network routing problem was discussed and tested using a hypothetical scenario where results showing the shortest path between data points in a typical communication network was calculated and display using JAVA programming language to implement it on Netbeans IDE 8.2. However, bellman-ford algorithm which is an algorithm that deals with negative edges does not produce the same output as the rest algorithms due to the data used in testing them all which was a limitation in the test.
TABLE OF CONTENT
Content Page
Title page i
Declaration ii
Approval Page iii
Dedication iv
Acknowledgements v
Table of Contents vi
List of Figures vii
List of Tables viii
Abstract ix
CHAPTER ONE: INTRODUCTION
Background of Study 1
Statement of the Problem 4
Aim and Objectives of the Study 5
Justification of the Study 5
Scope of the Study 6
Definition of Terms 6
CHAPTER TWO: LITERATURE REVIEW
2.1 Introduction 8
2.2 Graph Algorithm 10
2.2.1 Shortest Path Algorithms 10
2.2.2 Minimum Spanning Trees 22
2.3 Related Reviews 34
CHAPTER THREE: RESEARCH METHODOLOGY
3.1 Introduction 39
3.2 Pseudocode 39
3.2.1 Dijkstra’s Algorithm 39
3.2.2 Bellman-Ford Algorithm 40
3.2.3 Kruskal’s Algorithm 41
3.2.4 Prim’s Algorithm 42
3.3 Tool Used 43
3.4 Approach Used 43
CHAPTER FOUR: IMPLEMENTATION AND RESULT
4.1 Introduction 44
4.2 Hypothesis 45
4.3 Test 45
4.4 Result 47
4.5 Conclusion 52
4.6 Limitation 53
CHAPTER FIVE: SUMMARY, CONCLUSION AND RECOMMENDATION
5.1 Summary 54
5.2 Conclusion 54
5.3 Recommendation 55
5.4 Limitation of Study 55
REFERENCE 56
APPENDIX A 57
LIST OF FIGURES
Figures Pages
2.1 Undirected and Directed Graph 9
2.2.1 Undirected weighted Graph 11
2.2.1 Undirected weighted grap with nodes and edges 12
2.2.1 Dijkstra’s Shortest Path Algorithm 16
2.2.1 Bellman-Ford Algorithm 20
2.2.2 Minimum Spanning Tree for Kruskal Algorithm 27
2.2.2 Minimum Spanning Tree for Prim’s Algorithm 32
4.1 Typical network graph 43
4.3 Typical Communication network 46
4.4 output window showing the shortest path from 0 to 2. 48
4.4 Output window showing minimum path to reach all data
points using Kruskal’s Algorithm. 50
4.4 Output window showing minimum path to reach all data
points using Prim’s Algorithm. 51
LIST OF TABLES
Tables Pages
3.1 Pseudocode for Dijkstra’s Algorithm 39
3.2 Pseudocode for Bellman-Ford Algorithm 39
3.3 Pseudocode for Kruskal Algorithm 40
3.4 Pseudocode for Prim’s Algorithm 41
4.1 Inputs to Dijkstra’s algorithm 47
4.2 Inputs given to Dijkstra’s algorithm (Distance) 47
4.3 Determination of the shortest path Algorithm 48
