SINGLE SOURCE SHORTEST PATH PROBLEM

CONTENT
 Introduction
 Definition
 Basic Concept
 Methodology
 Application
 Complexity
 Explication
 Data stature
 Advantage
 Disadvantage
INTRODUCTION
 The Single-Source Shortest Path (SSSP) problem consists of finding the shortest
paths between a given vertex v and all other vertices in the graph. Algorithms for
unweighted graphs or weighted graphs Dijkstra solve this problem. One can use the
Dijkstra algorithm to each vertex in the graph in order to solve the problem.
 Dijkstra algorithm solves the shortest-path problem for any
✓ Weighted graphs,
✓ Directed graphs
✓ Having Non-Negative weights.
✓ It can handle graphs consisting of cycles, but negative weights will cause this algorithm
to produce incorrect results
INTRODUCTION
 Dijkstra's algorithm works correctly, because all edge weights are non-negative, and
the vertex with the least shortest-path estimate is always chosen.
 In the first iteration of the while loop, the source s is chosen and its adjacent vertices
have their est(v) set to
w((s, v)).
 In the second iteration, the vertex u with minimal w((s, u)) will be selected; then
those edges incident from u will be relaxed. Clearly, there exists no shorter path
from s to u than the single edge (s, u), because all weights are not negative, and any
path traced that uses an intermediate vertex is longer.
 Continuing this reasoning brings us to the conclusion that the algorithm, indeed,
computes the shortest paths.
DEFINITION

 It is used to determine the DISTANCE from S (Source) to every other V

(Vertex) in the graph
 This problem is mostly solved using Dijkstra, though in this case a single
result is kept and other shortest paths are discarded
 Input is weighted graph G= {E,V} and source vertex, such that all Edge weight
is Non Negative, where E is Edges and V is vertex
BASIC CONCEPTS

 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.
• Undirected Graphs: if for every pair of connected nodes, you can go from one node to the
other in BOTH DIRECTIONS.
• Directed Graphs: if for every pair of connected nodes, you can only go from one node to
another in a SPECIFIC DIRECTION. We use arrows instead of simple lines to represent
directed edges.
METHODOLOGY

 Now that you know more about this algorithm, let's see how it works behind the scenes with a a step-by-
step example.
 We have this graph:
METHODOLOGY
METHODOLOGY

 Set s as 0 and all others as ∞ because all other vertices are not visited yet.
 Unvisited nodes: {0,1,2,3,4,5,6}
 Since we are choosing to start at node 0 we can mark this node as visited. Equivalently, we cross it off
from the list of unvisited nodes and add a red border to the corresponding node.

 Unvisited nodes: {0,1,2,3,4,5,6}

METHODOLOGY
METHODOLOGY

 Now we need to start checking the distance from

node 0. to its adjacent nodes. As you can see, these
are nodes 1 and 2.
METHODOLOGY

 After updating the distances of the adjacent nodes, we need to:

• Select the node that is closest to the source node based on the current known distances.
• Mark it as visited.
• Add it to the path
METHODOLOGY

 If we check the list of distances, we can see that

node 1, has the shortest distance to the source
node (a distance of 2), so we add it to the path.
 We mark it with a red square in the list to
represent that it has been "visited" and that we
have found the shortest path to this node:
METHODOLOGY

 Unvisited nodes: {0,1,2,3,4,5,6}

 We cross it off from the list of unvisited
nodes:
METHODOLOGY

 Node 3 and 2 are both adjacent to nodes that are already in the path because they are directly
connected to node 0 and 1 respectively,
 as you can see below. These are the nodes that we will analyze in the next
 METHODOLOGY

Since we already have the distance from the source

node to node written (2) down in our list,

we don't need to update the distance this time.

We only need to update the distance from the

source node to the new adjacent node (node 3):

This distance is 7. Let's see why

METHODOLOGY

 To find the distance from the source node to another node (in this case, node 3.

 we add the weights of all the edges that form the shortest path to reach that node:
METHODOLOGY

 Now we need to repeat the process to find the shortest path from the source node to the new adjacent
node, which is node 3.
 You can see that we have two possible paths

 0 -> 1 -> 3 or
 0 -> 2 -> 3.
METHODOLOGY

But now we have another alternative. If we

choose to follow the path

0 -> 2 -> 3,
we would need to follow two edges

0 -> 2 and 2 -> 3

with weights 6 and 8, respectively, which

represents a total distance of 14.
METHODOLOGY

 Clearly, the first (existing) distance is shorter (7 vs.

14), so we will choose to keep the original path
 0 -> 1 -> 3
 We only update the distance if the new path is
shorter
 Therefore, we add this node to the path using the
first alternative:
 0 -> 1 -> 3
 We mark this node as visited and cross it off from
the list of unvisited nodes:
METHODOLOGY

 Now we repeat the process again.

 We need to check the new adjacent
nodes that we have not visited so far.
This time, these nodes are node 4 and
5 since they are adjacent to node 3.
 METHODOLOGY

•For node 4: the distance is 17 from the path 0 -> 1 -> 3 ->
4.

•For node 5: the distance is 22 from the path 0 -> 1 -> 3 ->
5.
 METHODOLOGY

We need to choose which unvisited node will be marked as

visited now.

In this case, it's node 4 because it has the shortest distance in

the list of distances.

We add it graphically in the diagram:

We also mark it as "visited" by adding a small red square in the

list:
METHODOLOGY

 And we repeat the process again. We check the

adjacent nodes: node 5 and node 6.
 We need to analyze each possible path that we
can follow to reach them from nodes that have
already been marked as visited and added to the
path.
METHODOLOGY
•The first option is to follow the path 0 -> 1 -> 3 -> 5,
• which has a distance of 22 from the source node (2 + 5 + 15).

• This distance was already recorded in the list of distances in a

previous step.
•The second option would be to follow the path 0 -> 1 -> 3 ->
4 -> 5, which has a distance of 23 from the source node (2 + 5
+ 10 + 6).

Clearly, the first path is shorter, so we choose it for node 5.

For node 6:

•The path available is 0 -> 1 -> 3 -> 4 -> 6, which has a

distance of 19 from the source node (2 + 5 + 10 + 2).
METHODOLOGY

 And we cross it off from the list of

unvisited nodes:
 METHODOLOGY

There are three different paths that we can take to reach node 5 from the
nodes that have been added to the path:
•Option 1: 0 -> 1 -> 3 -> 5 with a distance of 22 (2 + 5 + 15).
•Option 2: 0 -> 1 -> 3 -> 4 -> 5 with a distance of 23 (2 + 5 + 10 + 6).
•Option 3: 0 -> 1 -> 3 -> 4 -> 6 -> 5 with a distance of 25 (2 + 5 + 10 + 2 + 6).
EXAMPLE

u v
1
 

10
9
2 3
s 0 4 6

5 7

 
2
x y
EXAMPLE

u v
1
10 

10
9
2 3
s 0 4 6

5 7

5 
2
x y
EXAMPLE

u v
1
8 14

10
9
2 3
s 0 4 6

5 7

5 7
2
x y
EXAMPLE

u v
1
8 13

10
9
2 3
s 0 4 6

5 7

5 7
2
x y
EXAMPLE

u v
1
8 9

10
9
2 3
s 0 4 6

5 7

5 7
2
x y
EXAMPLE

u v
1
8 9

10
9
2 3
s 0 4 6

5 7

5 7
2
x y
SUMMARY

• 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.
APPLICATIONS

• It is used in finding Shortest Path.

• It is used in geographical Maps.
• To find locations of Map which refers to vertices of graph.
• Distance between the location refers to edges.
• It is used in IP routing to find Open shortest Path First.
• It is used in the telephone network.
• It's also called A* algorithm.
COMPLEXITY

 Time Complexity of Dijkstra's Algorithm is

 O(V2)
 but with min-priority queue it drops down to
 O(V+ElogV)
DATA STRUCTURE

 Min Heap

 Approach

 Greedy Approach
ADVANTAGES

 It is used in Google Maps

 It is used in finding Shortest Path.
 It is used in geographical Maps
 To find locations of Map which refers to vertices of graph.
 Distance between the location refers to edges.
 It is used in IP routing to find Open shortest Path First.
 It is used in the communication network.
DISADVANTAGES

 It do blind search so wastes lot of time while processing.

 It cannot handle negative edges.
 This leads to acyclic graphs and most often cannot obtain the right shortest
path.
 Thanks For listening