THE SHORTEST PATH PROBLEM

0
55

THE SHORTEST PATH PROBLEM (STATISTICS PROJECT TOPICS AND MATERIALS)

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.
1. 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…..