KOTEBE UNIVERSITY OF EDUCATION

COLLEGE OF SCIENCE AND MATHEMATICS EDUCATION

DEPARTMENT OF MATHEMATICS
This Project submitted to the department of mathematics in partial
fulfillment of the requirements for the degree of Bachelor of Science
in mathematics.

Project Title: - Graph theory of shortest path

Prepared By: -

Belete Brihanu

Advisor: -

[Link].

May,2024

Addis Ababa, Ethiopia

i
 DECLARATION

I declare that this project is based on my original work. I write this project by the knowledge I
get from the literatures and lectures. I have dually acknowledged and refereed all materials used
in this work. Kotebe University of education institute of natural and computational science can
also evoke penal action from the sources which have not been properly cited or acknowledged on
this project.
Signature Date

Student name: --------------------------- ------------------------ ---------------

Advisor name: ------------------------------ ----------------------- ----------------

Examiner name: --------------------------- ------------------------- ---------------

ii
Acknowledgement
First and foremost, praises and thanks to the God, the Almighty, for His showers of
blessings throughout project work to complete the project successfully. I would like to
express my deep and sincere gratitude to my project advisor Mr. Paulos. For his supporting,
advice, kindness and father more I have no word for his helping me at any time and situation

Finally, my thanks go to all the people who have supported me to complete the project work
directly or indirectly.

iii
Abstract
Graph theory is used for finding communities in networks. Graphs are used as device for
modeling and description of real world network systems such are: transport, water, electricity,
internet, work operations schemes in the process of production, construction, etc. Although the
content of these schemes differ among themselves, but they have also common features and
reflect certain items that are in the relation between each other. So in the scheme of transport
network might be considered manufacturing centers, and roads and rail links connected directly
to those centers. In this paper is designed the solution for an practical problem to find a
Minimum Spanning Tree by using Kruskal algorithm and graph search algorithm Dijsktra to
find the shortest path between two points, Also, for this case was developed a network model of
the transportation problem which is analyzed in detail to minimize shipment costs.

i
 TABLE OF CONTENT

Contents page
Acknowledgement.....................................................................................................................................iii
Abstract........................................................................................................................................................i
TABLE OF CONTENT.............................................................................................................................ii
CHAPTER ONE........................................................................................................................................1
1. INTRODUCTION.............................................................................................................................1
1.3. Statement of the problem...................................................................................................................2
1.4. Objective of the Project......................................................................................................................2
1.4.1. General objective.......................................................................................................................2
1.4.2. Specific objectives................................................................................................................2
CHAPTER TWO.......................................................................................................................................3
2. SHORTEST WEIGHTED PATHS..................................................................................................3
2.1. What is Graph.................................................................................................................................3
Example...............................................................................................................................................3
2.1.1. Types of Graph...........................................................................................................................4
2.1.2. Properties of Graph.............................................................................................................4
2.1.3. Trees, Degree and Cycle of Graph........................................................................................5
2.1.4. Graph Theory Algorithm......................................................................................................5
2.2. Definition And Example Shortest Path.............................................................................................6
2.3. Weighted Graphs and Their Representation....................................................................................6
2.4. SHORTEST WEIGHTED PATHS...................................................................................................7
2.5. Dijkstra’s algorithm...........................................................................................................................9
2.5. Applications of Dijkstra’s shortest path algorithm........................................................................11
CHAPTER THREE.................................................................................................................................13
Results and conclusion............................................................................................................................13
Conclusion................................................................................................................................................14
References................................................................................................................................................15

ii
 CHAPTER ONE
1. INTRODUCTION

Graphs are data structures used to represent "connections" between pairs of elements. These
elements are called nodes. They represent real-life objects, persons, or entities. The connections
between nodes are called edges. If we have a map which shows many cities with the routes
between it and we want to go from one to another…. If there are few cases we can enumerate all
the routes between the two points, then add up the distances on each route, and select the
shortest. But if we have a lot of cases we can’t find it easily, we should use an algorithm which
help us to find the shortest path and some applications need to find the shortest path and use it
(maps applications, network routing….), so the programmer of this applications need to write a
code which find the shortest path depending on shortest path algorithms. in competitive
programming: shortest path problems are one of the most important side in programming
contests so every competitive programmer needs to use shortest path algorithms.
A graph G is connected if and only if there exists a path that connects every pair of vertices in G.
A connected component of a graph G is a maximal subgraph of G that is connected; thus, a
connected graph has a single connected component. The distance between a pair of vertices u, v,
d(u, v), is equal to the minimum number of edges in a path connecting u and v. A shortest path
between two vertices u and v, is a path connecting u and v having length equal to d(u, v). The
eccentricity of a vertex v, ecc(v), is the greatest distance from v to another vertex in G. Consider
vertex v and, for each other vertex u, let Pv,u be the set of shortest paths that connect v and u.
In a network, we assume each site knows of one or more shortest paths to every other site, based
upon routing information for disseminating messages in the network. Given the links on the
paths, each site knows about the existence of a subset of the links in the network. In the network
discovery problem, we establish query sites that can probe the network via shortest paths and we
then attempt to determine the exact set of links in a network. Beerliova et al. [1] discuss online
algorithms to determine the minimum number of site queries required to discover all edges in a
network. In the network monitoring, or covering, problem we want to determine the status of all
lines that are known to be in a network based upon a set of site queries. In the shortest path cover
problem we want to cover every edge of a known graph representing a network by the shortest
paths from a subset of vertices in the graph. In this paper we consider two different models of
graph sampling via shortest paths, our goal being to minimize the number of required vertices as
query points.

1
 1.3. Statement of the problem

Like we saw shortest path problems is very important for competitive programmers and other
programmers which work on different projects so every programmer needs to solve a shortest
path problems using one of shortest path algorithms. And as we know there is many shortest path
algorithms and solving a shortest path problem depending on the algorithm that we use. So, what
is the cases and algorithms for shortest path? And which algorithm can we use on every case and
any of them is the better in every case?
1.4. Objective of the Project
1.4.1. General objective
The main aim of this project work is finding a path between two vertices (or nodes) in a graph
such that the sum of the weights of its constituent edges is minimized.

1.4.2. Specific objectives

 To determine and identify the concepts of the shortest path problem
 Provides a helpful tool to quantify & simplify the many moving parts of dynamic systems.
 Finding Pareto-optimal paths between two given nodes in a graph where each edge has several
associated costs, while minimizing several objectives.
 finding the shortest path between two vertices (or nodes) in a graph.
 Important for road network, operations, and logistics research.
 Provides a helpful tool to quantify & simplify the many moving parts of dynamic systems.

2
 CHAPTER TWO
2. SHORTEST WEIGHTED PATHS
In this chapter we will cover problems involving finding the shortest path between vertices in a
graph with weights (lengths) on the edges. One obvious application is in finding the shortest
route from one address to another, however shortest paths have many other application. We will
look at a version of the problem assuming we are finding distances from a single source to all
other vertices in the graph, and two variants depending on whether we allow negative edge
weights or not. We first introduce weighted graphs.
2.1. What is Graph
In Mathematics, a graph is a pictorial representation of any data in an organized manner. The
graph shows the relationship between variable quantities. In a graph theory, the graph represents
the set of objects, that are related in some sense to each other. The objects are basically
mathematical concepts, expressed by vertices or nodes and the relation between the pair of
nodes, are expressed by edges.

Definition

Graph Theory is the study of points and lines. In Mathematics, it is a sub-field that deals with the
study of graphs. It is a pictorial representation that represents the Mathematical truth. Graph
theory is the study of relationship between the vertices (nodes) and edges (lines).

Formally, a graph is denoted as a pair G (V, E).

Where V represents the finite set vertices and E represents the finite set edges.

Therefore, we can say a graph includes non-empty set of vertices V and set of edges E.

Example

Suppose, a Graph G=(V,E), where

Vertices, V={a, b, c, d}

Edges, E= {{a, b},{a, c},{b, c},{c, d}}

3
2.1.1. Types of Graph
The graphs are basically of two types, directed and undirected. It is best understood by the figure
given below. The arrow in the figure indicates the direction.

Directed Graph
In graph theory, a directed graph is a graph made up of a set of vertices connected by edges, in which the
edges have a direction associated with them.
Undirected Graph
The undirected graph is defined as a graph where the set of nodes are connected together, in which all the
edges are bidirectional. Sometimes, this type of graph is known as the undirected network.
Other types of graphs

 Null Graph: A graph that does not have edges.

 Simple graph: A graph that is undirected and does not have any loops or multiple edges.
 Multigraph: A graph with multiple edges between the same set of vertices. It has loops
formed.
 Connected graph: A graph where any two vertices are connected by a path.
 Disconnected graph: A graph where any two vertices or nodes are disconnected by a
path.
 Cycle Graph: A graph that completes a cycle.
 Complete Graph: When each pair of vertices are connected by an edge then such graph is
called a complete graph
 Planar graph: When no two edges of a graph intersect and are all the vertices and edges
are drawn in a single plane, then such a graph is called a planar graph
2.1.2. Properties of Graph

 The starting point of the network is known as root.

4
  When the same types of nodes are connected to one another, then the graph is known as
an assortative graph, else it is called a disassortative graph.
 A cycle graph is said to be a graph that has a single cycle.
 When all the pairs of nodes are connected by a single edge it forms a complete graph.
 A graph is said to be in symmetry when each pair of vertices or nodes are connected in
the same direction or in the reverse direction.
 When a graph has a single graph, it is a path graph.
2.1.3. Trees, Degree and Cycle of Graph
There are certain terms that are used in graph representation such as Degree, Trees, Cycle, etc.
Let us learn them in brief.

Trees: A tree in a graph is the connection between undirected networks which are having only
one path between any two vertices. It was introduced by British mathematician Arthur Cayley in
1857. The graph trees have only straight lines between the nodes in any specific direction but do
not have any cycles or loops. Therefore trees are the directed graph.

Degree: A degree in a graph is mentioned to be the number of edges connected to a vertex. It is

denoted deg(v), where v is a vertex of the graph. So basically it the measure of the vertex.

Cycle: A cycle is a closed path in a graph that forms a loop. When the starting and ending point
is the same in a graph that contains a set of vertices, then the cycle of the graph is formed. When
there is no repetition of the vertex in a closed circuit, then the cycle is a simple cycle. The cycle
graph is denoted by Cn.

 A cycle that has an even number of edges or vertices is called Even Cycle.
 A cycle that has an odd number of edges or vertices is called Odd Cycle.
2.1.4. Graph Theory Algorithm
The procedure to draw a graph for any given function or to calculate any function is the
algorithm of the graph. Basically, there are predefined steps or sets of instructions that have to be
followed to solve a problem using graphical methods. There are different types of algorithms
which the graph theory follows, such as;

 Dijkstra's Algorithm
 Bellman-Ford algorithm
 Boyuvke’s algorithm
 Ford–Fulkerson algorithm
 Edmonds–Karp algorithm and many more.

5
2.2. Definition And Example Shortest Path
Definition
In graph theory, one of the most fundamental and widely studied problems is the shortest path
problem. This problem involves finding the shortest path between two nodes (or vertices) in a
graph, where the graph is a collection of nodes connected by edges. Each edge may have a
weight or cost associated with it, representing the "distance" between the nodes it connects.
The shortest path problem can be defined for graphs whether undirected, directed, or mixed. It is
defined here for undirected graphs; for directed graphs the definition of path requires that
consecutive vertices be connected by an appropriate directed edge.
Two vertices are adjacent when they are both incident to a common edge. A path in an undirected
graph is a sequence of vertices.
p=( v 1 , v 2 ,… v n ) ∈ V ×V … ×V such that v iis adjacent to v i+1 for 1 ≤i<n such that a path p is
called a path of length n−1 from v 1 to v n. (The v i v i are variables; their numbering here relates to
their position in the sequence and needs not to relate to any canonical labeling of the vertices.)
The problem is also sometimes called the single-pair shortest path problem, to distinguish it
from the following variations:

 The single-source shortest path problem, in which we have to find shortest paths
from a source vertex v to all other vertices in the graph.
 The single-destination shortest path problem, in which we have to find shortest
paths from all vertices in the directed graph to a single destination vertex v. This can
be reduced to the single-source shortest path problem by reversing the arcs in the
directed graph.
 The all-pairs shortest path problem, in which we have to find shortest paths
between every pair of vertices v, v' in the graph.
These generalizations have significantly more efficient algorithms than the simplistic approach
of running a single-pair shortest path algorithm on all relevant pairs of vertices.

2.3. Weighted Graphs and Their Representation

Many applications of graphs require associating weights or other values with the edges of a
graph. Such graphs can be formally defined as follows.
Definition 1. (Weighted and Edge-Labeled Graphs). A weighted graph or an edgelabeled graph
is a triple G = (E, V, w) where w: E → L is a function mapping edges or directed edges to their
values, and L is the set of possible values.
In a graph, if the data associated with the edges are real numbers (L ⊆ R), we often use the term
“weight” to refer to the values, and use the term “weighted graph” to refer to the graph. In the

6
general case, we use the terms “edge label” or “edge values” to refer to the values. Weights or
other values on edges could represent many things, such as a distance, or a capacity, or the
strength of a relationship.

Fig. An example directed weighted graph

This chapter described three different representations of graphs suitable for parallel algorithms,
edge sets, adjacency tables, and adjacency sequences.
We can extend all of these representations to support edge values by separately representing the
function from edges to values using a table (mapping)—the table maps each edge (or arc) to its
value. This representation allows looking up the edge value of an edge e = (u, v) by using a table
lookup. We call this an edge table.
Example 13.4. For the weighted graph in Example 13.2, the edge table is: W = {(1, 3) 7→ 0.7,
(1, 4) 7→ −1.5, (3, 4) 7→ −2.0, (4, 2) 7→ 3.0}
A nice property of an edge table is that it works uniformly with all representations of the
structure of a graph, and is clean since it separates the edge values from the structural
information. However keeping the edge table separately creates redundancy, wasting space and
possibly requiring extra work accessing the edge values. The redundancy can be avoided by
storing the edge values directly with the edge information. For example, using edge tables makes
edge sets redundant so there is typically no need to keep a separate edge set. Adjacency tables
can be extended to include the edge values by replacing the set of neighbors of a vertex v with a
table that maps each neighbor u to the edge value w(v, u). Adjacency sequences can be extended
by creating a sequence of neighbor-value pairs for each out edge of a vertex.
2.4. SHORTEST WEIGHTED PATHS
Example: For the weighted graph in Example 13.2, the adjacency table representation is
G = {1 7→ {3 7→ 0.7, 4 7→ −1.5} , 3 7→ {4 7→ −2.0} , 4 7→ {2 7→ 3.0}} , and

7
the adjacency sequence representation is (assuming sequences are 1 based):
G = h h(3, 0.7), (4, −1.5)i,h i,h(4, −2.0)i, h(2, 3.0).
Consider a weighted graph G = (V, E, w), w : E → R. The graph can be either directed or
undirected. For convenience we define w(u, v) = ∞ if (u, v) 6∈ E. We define the weight of a path
as the sum of the weights of the edges along that path.
Example: In the following graph the weight of the path h s, a, b, e i is 6. The weight of the path h
s, a, b, s i is 10.

For a weighted graph G(V, E, w) a shortest (weighted) path from vertex u to vertex v is a path
from u to v with minimum weight. There might be multiple paths with equal weight, and if so
they are all shortest weighted paths from u to v. We use σG(u, v) to indicate the weight of a
shortest path from u to v. In shortest path problems, we are required to find the shortest
(weighted) path between vertices, or perhaps just the weight of such paths.
Question 1. What is the (weighted) shortest path from s to e?
In the graph above, the shortest path from s to e is hs, a, b, ei with weight 6.
Question 2. What happens if we change the weight of the edge (b, s) from 7 to −7?
If we change the weight of the edge (b, s) to −7 the shortest path between s and e has weight −∞
since a path can keep going around the cycle h s, a, b, s i reducing its weight by 4 each time
around.
Recall that a path allows repeated vertices—-a simple path does not. For this reason, when
computing shortest paths we will need to be careful about cycles of negative weight. As we will
see, even if there are no negative weight cycles, negative edge weights make finding shortest
paths more difficult. We will therefore first consider the problem of finding shortest path when
there are no negative edge weights.

8
Computing shortest paths is important in many practical applications. In fact, there are several
variants of this problem such as the “single source” and the “multiple source” versions, both with
or without negative weights.

2.5. Dijkstra’s algorithm

Dijkstra’s algorithm, named after Dutch computer scientist Edsger W. Dijkstra, is a fundamental
algorithm used in graph theory and computer science for finding the shortest path between nodes
in a graph with non-negative edge weights. Originally designed to solve the single-source
shortest path problem, Dijkstra’s algorithm efficiently determines the shortest path from a
designated starting node to all other nodes in the graph. Its simplicity and effectiveness make it a
widely used tool in various applications, including network routing protocols, transportation
networks, and data processing systems.

How Dijkstra algorithm Work?

The algorithm works by maintaining a set of vertices that have already been visited, and a set of
vertices that have not yet been visited. The algorithm starts at the source vertex and adds it to the
set of visited vertices. Then, it repeatedly finds the vertex in the set of unvisited vertices that has
the shortest known path to the source vertex, and adds that vertex to the set of visited vertices.
This process continues until all vertices have been visited.

The Dijkstra algorithm is a greedy algorithm, which means that it makes the best possible choice
at each step, without considering the future consequences of its decisions. In the case of Dijkstra
algorithm, the best possible choice is to add the vertex with the shortest known path to the source
vertex to the set of visited vertices.

The Dijkstra algorithm is a very efficient algorithm for finding the shortest paths in a graph. Its
time complexity is O(V log V), where V is the number of vertices in the graph.

Example of Dijkstra algorithm

Here is an example of Dijkstra algorithm that is discussed below.

9
Step 1 : Start with a weighted graph.

Step 2 : Choose a starting vertex and assign infinity path values to all other devices.

Step 3 : Go to each vertex and update its path length.

Step 4 : If the path length of the adjacent vertex is less than new path length, don’t update it.

Step 5 : Avoid updating path lengths of already visited vertices.

10
 Step 6 : After each iteration, we pick the unvisited vertex with the least path length. So we
choose 5.

Step 7 : Notice how the rightmost vertex has its path length updated twice.

Step 8 : Repeat until all the vertices have been visited.

2.5. Applications of Dijkstra’s shortest path algorithm

Dijkstra’s algorithm is one of the most popular algorithms for solving many single-source shortest path
problems having non-negative edge weight in the graphs i.e., it is to find the shortest distance between
two vertices on a graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published
three years later.

Dijkstra’s Algorithm has several real-world use cases, some of which are as follows:

1. Digital Mapping Services in Google Maps: Many times we have tried to find the distance in G-
Maps, from one city to another, or from your location to the nearest desired location. There
encounters the Shortest Path Algorithm, as there are various routes/paths connecting them but it
has to show the minimum distance, so Dijkstra’s Algorithm is used to find the minimum distance
between two locations along the path. Consider India as a graph and represent a city/place with a
vertex and the route between two cities/places as an edge, then by using this algorithm, the

11
 shortest routes between any two cities/places or from one city/place to another city/place can be
calculated.
2. Social Networking Applications: In many applications you might have seen the app suggests
the list of friends that a particular user may know. How do you think many social media
companies implement this feature efficiently, especially when the system has over a billion
users. The standard Dijkstra algorithm can be applied using the shortest path between users
measured through handshakes or connections among them. When the social networking graph is
very small, it uses standard Dijkstra’s algorithm along with some other features to find the
shortest paths, and however, when the graph is becoming bigger and bigger, the standard
algorithm takes a few several seconds to count and alternate advanced algorithms are used.
3. Telephone Network: As we know, in a telephone network, each line has a bandwidth, ‘b’. The
bandwidth of the transmission line is the highest frequency that line can support. Generally, if
the frequency of the signal is higher in a certain line, the signal is reduced by that line.
Bandwidth represents the amount of information that can be transmitted by the line. If we
imagine a city to be a graph, the vertices represent the switching stations, and the edges represent
the transmission lines and the weight of the edges represents ‘b’. So as you can see it can fall into
the category of shortest distance problem, for which the Dijkstra is can be used.
4. IP routing to find Open shortest Path First: Open Shortest Path First (OSPF) is a link-state
routing protocol that is used to find the best path between the source and the destination router
using its own Shortest Path First. Dijkstra’s algorithm is widely used in the routing protocols
required by the routers to update their forwarding table. The algorithm provides the shortest cost
path from the source router to other routers in the network.
5. Flighting Agenda: For example, If a person needs software for making an agenda of flights for
customers. The agent has access to a database with all airports and flights. Besides the flight
number, origin airport, and destination, the flights have departure and arrival time. Specifically,
the agent wants to determine the earliest arrival time for the destination given an origin airport
and start time. There this algorithm comes into use.
6. Designate file server: To designate a file server in a LAN (local area network), Dijkstra’s
algorithm can be used. Consider that an infinite amount of time is required for transmitting files
from one computer to another computer. Therefore to minimize the number of “hops” from the

12
 file server to every other computer on the network the idea is to use Dijkstra’s algorithm to
minimize the shortest path between the networks resulting in the minimum number of hops.
7. Robotic Path: Nowadays, drones and robots have come into existence, some of which are
manual, some automated. The drones/robots which are automated and are used to deliver the
packages to a specific location or used for a task are loaded with this algorithm module so that
when the source and destination is known, the robot/drone moves in the ordered direction by
following the shortest path to keep delivering the package in a minimum amount of time.

CHAPTER THREE
Results and conclusion

As we saw shortest path algorithms is very important for a lot of problems such as: web graph
and networks routing. As a result of his research: 1. we find that the best algorithms to find the
shortest path in unweighted and undirected graph is BFS or DFS in o(V+E) time complexity. 2.
To find the single source shortest path without the negative weights Dijkstra’s algorithm is the
best way with O(V2 ) or O((V+E) log(V)) in other implementations. 3. To find the single source
shortest path with the negative weights Bellman-Ford algorithm is the best way with O(V+E)
time complexity. 4. To find All pairs shortest path in the sparse algorithm the best algorithm is
Johnson algorithm with O(V2+VE) and in large graphs Floyd-Warshall is the best with O(V3 )
time complexity. 5. All of the mentioned algorithms before can work with negative weights but
Dijkstra’s algorithms cannot work with negative weights or detect negative weights cycle.

Dijkstra’s were tested using predefined test cases and automated checking system available in
the websites[10][11][12].Some information such as the number of test cases, results, author, date
of submission, and programming language used for each algorithm are provided.

13
 Conclusion

 Graphs are used to model connections between objects, people, or entities. They have two main
elements: nodes and edges. Nodes represent objects and edges represent the connections between
these objects.
 Dijkstra's Algorithm finds the shortest path between a given node (which is called the "source
node") and all other nodes in a graph.
 This algorithm uses the weights of the edges to find the path that minimizes the total distance
(weight) between the source node and all other nodes.

14
References
1. Skiena, S.S. and M.A. Revilla, Programming challenges: The programming contest training manual.
2006: Springer Science & Business Media.
2. Halim, S. and F. Halim, Competitive Programming
3: The New Lower Bound of Programming Contests: Handbook for ACM ICPC and IOI Contestants.
2013. 3. Cormen, T.H., et al., Introduction to algorithms second edition. 2001, The MIT Press.
4. Chen, J.-C., Dijkstra’s shortest path algorithm. Journal of Formalized Mathematics, 2003. 15: p. 144-
157.
5. Johnson, D.B., A note on Dijkstra's shortest path algorithm. Journal of the ACM (JACM), 1973. 20(3):
p. 385-388.
6. Goldberg, A.V. and T. Radzik, A heuristic improvement of the Bellman-Ford algorithm. Applied
Mathematics Letters, 1993. 6(3): p. 3-6.
7. Katz, G.J. and J.T. Kider Jr. All-pairs shortest-paths for large graphs on the GPU. in Proceedings of
the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware. 2008. Euro graphics
Association.

8. Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihalak, and L. S. Ram.

Network discovery and verification. In Proceedings of the 31st International Workshop on
Graph-Theoretic Concepts in Computer Science (WG 2005), volume LNCS 3787, pages 127–
138. Springer, 2005.
9. A. Brandst¨adt, V. B. Le, and J. P. Spinrad. Graph classes: a survey. Society for Industrial and
Applied Mathematics, Philadelphia, PA, USA, 1999.
10. M. R. Garey and D. S. Johnson. Computer and Intractability: A Guide to the Theory of NP-
Completeness. W. H. Freeman, 1979.

15
16
17