Analysis of Dijkstra's Algorithm in Solving Shortest Path Problems

This report delves into the shortest path problem, a fundamental concept in computer networks and map-related systems, with the primary objective of evaluating Dijkstra's Algorithm. It begins by introducing the shortest path problem, explaining its representation through graphs, and defining key terms such as vertices, edges, and weights. The report outlines the motivation behind studying the problem, emphasizing the need to understand graph representations, algorithm implementations, and evaluation methods. The core of the report involves a problem statement that requires calculating the shortest path and alternative paths considering distance and fare between two cities, including the ability to remove nodes and recalculate routes. The solution section details Dijkstra's Algorithm, explaining its logic and implementation, including the use of adjacency matrices and the process of assigning labels to vertices to determine the shortest path. The report concludes by evaluating the algorithm's time complexity and discussing potential improvements using artificial intelligence techniques. The report also includes references to relevant literature and provides pseudocode for Dijkstra's Algorithm.

Title
Department name, College name with full address
Your email address
Abstract—Nowadays, in computer networks, the routing is based on
the shortest path problem. This will help in minimizing the overall
costs of setting up computer networks. New technologies such as
map-related systems are also applying the shortest path problem. This
paper’s main objective is to evaluate the Dijkstra’s Algorithm n
solving the shortest path problem.
I. INTRODUCTION
THE shortest path problem is a 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 the 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. However, only several of the most popular
conventional shortest path algorithms along with one that uses
genetic algorithm are going to be discussed in this paper, and
they are as follows:
1. Dijkstra’s Algorithm
II. MOTIVATION
 To determine and identify the concepts of the shortest
path problem.
 To determine the representation of graphs in computer
in order to solve the shortest path problem, as well as to
understand the different basic terms of a graph.
 To explain the general concepts and the
implementations of Dijkstra’s Algorithm.
 To evaluate each algorithm, and presents the
evaluations’ results.
III. PROBLEM STATEMENT
Calculate shortest path and alternative path(Re-routing) from
source to destination considering distance and fare.
There are two cities as Source and Destination. To travel from
Source city to Destination city we need to pass many cities or
highways.
We are considering multiple cities in between and various ways
to reach destination from source.
There are two parameters to be considered in this case.
We are considering distance and fare from source to destination.
If a bus passenger wants to travel from Source to destination he
can select any route or any price.
Price is irrespective to the distance. If any city or a node is
neglected, then program should be able to display the shortest
path without considering that node

Tasks involved:
1. Calculate and display the Shortest Distance from
source node to destination
2. Calculate and display the fare from source to
destination
3. Ask user to provide an input variable to remove any
node from nodes available between source and
destination excluding those two.
4. Calculate and display new shortest route and fare
5. Print a statement “Paths and fares other than the
shortest path”
6. Display all the possible paths and fare from source to
destination other than the shortest path displayed above
IV. LITERATURE REVIEW
As mentioned earlier, a graph can be used to represent a map
where the cities are represented by vertices and the routes or
roads are represented by edges within the graph. In this section,
a graph representation of a map is explained further, and brief
descriptions and implementations of the four shortest path
algorithms being studied are presented.
Representation of the Graph
In order to represent a graph in a computer we will use
adjacency matrix a. The dimension of the matrix will be equal to
(n x n), where n is number of vertices in graph. The element of
matrix a[i][j] is identified by an edge that connects the i-th and j-
th vertices; the value here represents the weight of the
corresponding edge. However, if there is no edge between
vertices i and j, the value in (a[i][j]) will be equal to infinity. An
array of edges is another common representation of the graph. If
m is the number of edges in a graph, then in order to represent
the graph we have to use m x 3 twodimensional arrays; in each
row, the first vertex, the second vertex, and the edge that
connects them are also stored. The benefit of using an array of
edges in comparison to adjacency matrix is when there is more
than one edge that connects two vertices we cannot use
adjacency matrix in order to represent graph.
V. SOLUTION/APPROACH
Dijkstra’s Algorithm:
Explanation and Implementation For each vertex within a graph
we assign a label that determines the minimal length from the
starting point s to other vertices v of the graph. In a computer we
can do it by declaring an array d[]. The algorithm works
sequentially, and in each step it tries to decrease the value of the
label of the vertices. The algorithm stops when all vertices have
been visited. The label at the starting point s is equal to zero
(d[s]=0); however, labels in other vertices v are equal to infinity
(d[v]=∞), which means that the length from the starting point s
to other vertices is unknown. In a computer we can just use a
very big number in order to represent infinity. In addition, for
each vertex v we have to identify whether it has been visited or
not. In order to do that, we declare an array of Boolean type
called u[v], where initially, all vertices are assigned as unvisited
(u[v] = false). The Dijkstra’s algorithm consists of n iterations.
If all vertices have been visited, then the algorithm finishes;
otherwise, from the list of unvisited vertices we have to choose
the vertex which has the minimum (smallest) value at its label
(At the beginning, we will choose a starting point s). After that,
we will consider all neighbors of this vertex (Neighbors of a
vertex are those vertices that have common edges with the initial
vertex). For each unvisited neighbor we will consider a new
length, which is equal to the sum of the label’s value at the
initial vertex v (d[v]) and the length of edge l that connects
them. If the resulting value is less than the value at the label,
then we have to change the value in that label with the newly
obtained value
d [ neighbors ] = min ( d [ neighbors ] , d[ v ] + l )
After considering all of the neighbors, we will assign the initial
vertex as visited (u[v] = true). After repeating this step n times,
all vertices of the graph will be visited and the algorithm
finishes or terminates. The vertices that are not connected with
the starting point will remain by being assigned to infinity. In
order to restore the shortest path from the starting point to other
vertices, we need to identify array p [], where for each vertex,
where v ≠ s, we will store the number of vertex p[v], which
penultimate vertices in the shortest path. In other words, a
complete path from s to v is equal to the following statement
P = ( s , … , p [ p [ p [ v ] ] ] , p [ p [ v ] ] , p [ v ] , v )

Fig. Pseudo code for Dijkstra’s Algorithm
VI. CONCLUSION
After evaluating the algorithm through various test cases it was
found that the computed Time Complexity for the Dijkstra’s
Algorithm is
O(N2 + M);
Where ‘N’ is the number of Nodes/Vertices and ‘M’ are the
number of Edges
For a complete graph where all the edges are visited the time
complexity becomes
O(N2)
Where ‘N’ is the number of Nodes/Vertices
show that these algorithms are acceptable in terms of their
overall performance in solving the shortest path problem. In
addition, other artificial intelligence techniques such as fuzzy
logic and neural networks can also be implemented in
improving existing shortest path algorithms in order to make
them more intelligent and more efficient
VII. REFERENCES
[1] Abraham and D. Delling. A hub-based labeling algorithm
for shortest paths in road networks. Experimental Algorithms,
2011.
[2] Abraham, D. Delling, A. Goldberg, and R. Werneck.
Hierarchical hub labelings for shortest paths. AlgorithmsESA
2012, 2012.
[3] Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck.
Highway dimension, shortest paths, and provably efficient
algorithms. Proceedings of the Twenty-First Annual ACM-
SIAM Symposium on Discrete Algorithms, pages 782–793,
2010.
[4] R. Agarwal, P. B. Godfrey, and S. Har-Peled. Approximate
distance queries and compact routing in sparse graphs. IEEE
INFOCOM, pages 1754–1762, 2011.
[5] A. V. Aho and J. E. Hopcroft. The Design and Analysis of
Computer Algorithms. AddisonWesley Longman Publishing
Co., Inc., Boston, MA, USA, 1st edition, 1974.
[6] W. Aiello, F. Chung, and L. Lu. A random graph model for
massive graphs. STOC, 2000.
[7] https://en.wikipedia.org/wiki/Dijkstra
%27s_algorithm#Pseudocode