Application of Graph Algorithm in solving Network Routing Problem

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

ContentPage

Title pagei

Declarationii

Approval Pageiii

Dedicationiv

Acknowledgementsv

Table of Contentsvi

List of Figuresvii

List of Tablesviii

Abstractix

CHAPTER ONE: INTRODUCTION

Background of Study1

Statement of the Problem4

Aim and Objectives of the Study5

Justification of the Study5

Scope of the Study6

Definition of Terms6

CHAPTER TWO: LITERATURE REVIEW

2.1Introduction8

2.2Graph Algorithm10

2.2.1Shortest Path Algorithms10

2.2.2Minimum Spanning Trees22

2.3Related Reviews34

CHAPTER THREE: RESEARCH METHODOLOGY

3.1Introduction39

3.2Pseudocode39

3.2.1 Dijkstra’s Algorithm39

3.2.2Bellman-Ford Algorithm40

3.2.3Kruskal’s Algorithm41

3.2.4Prim’s Algorithm42

3.3Tool Used43

3.4Approach Used43

CHAPTER FOUR: IMPLEMENTATION AND RESULT

4.1Introduction44

4.2Hypothesis45

4.3Test45

4.4Result47

4.5Conclusion52

4.6Limitation53

CHAPTER FIVE: SUMMARY, CONCLUSION AND RECOMMENDATION

5.1Summary54

5.2Conclusion54

5.3Recommendation55

5.4Limitation of Study55

REFERENCE56

APPENDIX A57

LIST OF FIGURES

FiguresPages

2.1  Undirected and Directed Graph9

2.2.1Undirected weighted Graph11

2.2.1 Undirected weighted grap with nodes and edges12

2.2.1Dijkstra’s Shortest Path Algorithm16

2.2.1Bellman-Ford Algorithm20

2.2.2Minimum Spanning Tree for Kruskal Algorithm27

2.2.2Minimum Spanning Tree for Prim’s Algorithm32

4.1Typical network graph43

4.3Typical Communication network46

4.4output window showing the shortest path from 0 to 2.48

4.4Output window showing minimum path to reach all data 

points using Kruskal’s Algorithm.50

4.4Output window showing minimum path to reach all data 

points using Prim’s Algorithm.51

LIST OF TABLES

TablesPages

3.1Pseudocode for Dijkstra’s Algorithm39

3.2Pseudocode for Bellman-Ford Algorithm39

3.3Pseudocode for Kruskal Algorithm40

3.4Pseudocode for Prim’s Algorithm41

4.1Inputs to Dijkstra’s algorithm47

4.2 Inputs given to Dijkstra’s algorithm (Distance)47

4.3Determination of the shortest path Algorithm48