Application of Graph Algorithm in solving Network Routing Problem

Innocent Ujah 111 PAGES (12242 WORDS) Project
Subscribe to access this work and thousands more

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



Subscribe to access this work and thousands more
Overall Rating

0

5 Star
(0)
4 Star
(0)
3 Star
(0)
2 Star
(0)
1 Star
(0)
APA

Innocent, U (2019). Application of Graph Algorithm in solving Network Routing Problem. Afribary.com: Retrieved October 17, 2019, from https://afribary.com/works/cover-page

MLA 8th

Ujah, Innocent. "Application of Graph Algorithm in solving Network Routing Problem" Afribary.com. Afribary.com, 07 Oct. 2019, https://afribary.com/works/cover-page . Accessed 17 Oct. 2019.

MLA7

Ujah, Innocent. "Application of Graph Algorithm in solving Network Routing Problem". Afribary.com, Afribary.com, 07 Oct. 2019. Web. 17 Oct. 2019. < https://afribary.com/works/cover-page >.

Chicago

Ujah, Innocent. "Application of Graph Algorithm in solving Network Routing Problem" Afribary.com (2019). Accessed October 17, 2019. https://afribary.com/works/cover-page