THE SHORTEST PATH PROBLEM

TABLE OF CONTENT

Title page

Certification

Dedication

Acknowledgement

Abstract

Table of Content

Chapter One: Introduction to the Shortest Path Problem

1.1       Preamble

1.2       Aims and Objectives of Study

1.3       Scope of Study

1.4       Limitations of Study

1.5       Motivation of Study

1.6       Assumption

1.7       Applications of the Shortest Path Problem

Chapter Two: Literature Review

Chapter Three: Mathematical Background

3.1 Introduction

3.2       The Label Algorithm – Brief description

3.3       Mono–Objective Case

3.4       Data Structure for Set X

3.5       Multi-Objective Case

3.6       Theory of the Dijkstra’s Algorithm

Chapter Four:  Real Life Problem

4.1       Sketch of the Road Network under Study

4.2       Representation of the Problem in a Directed and Weighted Graph

4.3       Dijktra’s Algorithm Solution Method

4.4       Analysis of the Solution

Chapter Five: Summary, Conclusion and Recommendations

5.1       Summary

5.2       Conclusion

5.3       Recommendation

            References

ABSTRACT

The Shortest Path Problem (SPP) requires the determination of the minimum route or path between a source node and a destination node in a network. In this work, we determined the shortest path between two locations in a road network using the Dijkstra’s Algorithm. The real life navigation problem is represented in a directed graph and the Dijkstra’s Algorithm was used to determine the shortest distance between a single source node and the destination node.

CHAPTER ONE

INTRODUCTION TO SHORTEST PATH PROBLEM

1.1            Preamble

The shortest path problem is the problem of finding the shortest path or route from a starting point to a final destination. Generally, in order to represent the shortest path problem we use graphs. A graph is a mathematical abstract object, which contains sets of vertices and edges. Edges connect pairs of vertices. Along the edges of a graph it is possible to walk by moving from one vertex to other vertices. Depending on whether or not one can walk along edges by both sides or by only one side determines if the graph is a directed graph or an undirected graph. In addition, lengths of edges are often called weights, and the weights are normally used for calculating the shortest path from one point to another point. In the real world it is possible to apply the graph theory to different types of scenarios. For example, in order to represent a map we can use a graph, where vertices represent cities and edges represent routes that connect the cities. If routes are one-way then the graph will be directed; otherwise, it will be undirected. There exist different types of algorithms that solve the shortest path problem. Dijkstra’s Algorithm was used in this work while others were discussed in the literature review.

1.2      Aims and Objectives of the Study

1.     To study, determine and identify the shortest path in a network.

2.     To explain the general concept of the Dijkstra’s algorithm.

To use Dijkstra’s algorithm method to evaluate the shortest path between a source node and a destination node in a road network.....

For more Mathematics Projects click here

================================================================

Item Type: Project Material  |  Size: 36 pages  |  Chapters: 1-5

Format: MS Word  |  Delivery: Within 30Mins.

================================================================

DOWNLOAD THIS PROJECT MATERIAL NOW! CLICK HERE!

Share: