+234 813 0686 500
+234 809 3423 853
info@grossarchive.com

Application of Graph Algorithm in solving Network Routing Problem

• Type:Project
• Pages:111
• Format:Microsoft Word
(Computer Science Project Topics & Materials)

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

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

Application of Graph Algorithm in solving Network Routing Problem

Details

 Type Project Department Computer Science Project ID CPU1641 Price ₦3,000 (\$20) No of Pages 111 Pages Format Microsoft Word

Details

 Type Project Department Computer Science Project ID CPU1641 Price ₦3,000 (\$20) No of Pages 111 Pages Format Microsoft Word

Related Works

Credit card fraud has been a common theft process around the globe recently. This project looks into solving and minimizing the risk of credit card fraud using AI (Artificial Intelligence) models.... Continue Reading
ABSTRACT Computer supported collaborative applications on overlay networks are gaining popularity among users who are geographically dispersed. Examples of these kinds of applications include video-conferencing, distributed database replication, and online games. This type of application requires a multicasting subnetwork, using which messages... Continue Reading
ABSTRACT The Transmission Control Protocol (TCP) wad designed to provide reliable end-to-end delivery of data over unreliable networks. In practice most TCP deployments have been carefully designed in the context of wired networks. Ignoring the properties of wireless Ad hoc Network can lead to TCP implementations with poor performance. In order to... Continue Reading
ABSTRACT A mobile ad-hoc network (MANET) consists of wireless mobile hosts (nodes) that communicate with each other over wireless link, in the absence of a fixed infrastructure. Routes between two hosts in MANET may consists of hops through other hosts in the network, due to the limitation of broadcasting range of each host Movement of hosts... Continue Reading
ABSTRACT This project work, is a computerization it Performance evaluation of routing algorithm using NS2 of an organization. Full duplex asynchronous data transfer system based on a single-phase two-line coding. (a) Data is transmitted from a primary module PM to a secondary module SM, while data is transmitted from the secondary module SM to the... Continue Reading
ABSTRACT Multicast routing is an effective way to communicate among multiple hosts in a network. It outperforms the basic broadcast strategy by sharing resources along general links, while sending information to a set of predefined multiple destinations concurrently. However, it is vulnerable to component failure in ad hoc network due to the lack... Continue Reading
ABSTRACT Interest in large-scale sensor networks for both civilian and military applications is burgeoning. The deployment of such networks will require new approaches in resource discovery, query processing and data routing. This paper presents a framework and some analytic results for query satisfaction and data routing in networks consisting of... Continue Reading
Abstract This work investigates an improved protection solution based on the use of artificial neural network on the 330kV Nigerian Network modelled using Matlab R2014a. Measured fault voltages and currents signals decomposed using the discrete Fourier transform implemented via fast Fourier transform are fed as inputs to the neural network. The... Continue Reading
ABSTRACT Multicast routing is an effective way to communicate among multiple hosts in a network. It outperforms the basic broadcast strategy by sharing resources along general links, while sending information to a set of predefined multiple destinations concurrently. However, it is vulnerable to component failure in ad hoc network due to the lack... Continue Reading
ABSTRACT A channel allocation algorithm in a cellular network consists of two parts: a channel acquisition algorithm and a channel selection algorithm. Some of the previous works in this field focused on centralized approaches to allocating channels. But, centralized approaches are neither scalable nor reliable. Recently, distributed dynamic... Continue Reading