Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Dijkstra’s Shortest Path Algorithm
2.1.
Working on Paths in Dijkstra’s Shortest Path Algorithm
3.
Applications of Dijkstra's Algorithm
4.
Pseudo Code
5.
Pictorial Way Representation
6.
Implementation in Python
7.
Output
7.1.
Time Complexity
7.2.
Space Complexity
8.
Frequently Asked Questions
8.1.
Which data structure is used in Dijkstra's algorithm?
8.2.
Does Dijkstra's algorithm always find the shortest path?
8.3.
Is Dijkstra a DFS or a BFS?
8.4.
Where is the shortest path algorithm used?
8.5.
Does Google Maps use Dijkstra?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Paths in Dijkstra’s Shortest Path Algorithm

Author Kanak Rana
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

graph is a pictorial way of a collection of things where some object pairs are linked together. Vertices are the points used to describe related items, while edges are the connections between them.

Paths in Dijkstra’s Shortest Path Algorithm

Paths in Dijkstra’s Shortest Path Algorithm are a part of the graph data structure. 

Let's start with the definition and then the coding part as well.

Dijkstra’s Shortest Path Algorithm

To acquire the shortest path tree from a single source node, Dijkstra's algorithm creates a set of nodes with the smallest distance from the source

Paths in Dijkstra’s Shortest Path Algorithm

NOTE -The shortest distance between two vertices may not include all of the graph's vertices, which distinguishes it from the minimal spanning tree.

Working on Paths in Dijkstra’s Shortest Path Algorithm

Dijkstra's algorithm implies that each subpath P -> U of the shortest path Q -> U connecting vertices Q and U is also the shortest route connecting vertices P and U.

Djikstra reversely used this property, i.e., we state the distance of each vertex from the initial vertex. Then we go from node to node, identifying the shortest subpath between them.

The algorithm takes a greedy approach in that it seeks the following best answer in the hope that the result is the best solution for the entire problem.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Applications of Dijkstra's Algorithm

  • To determine the shortest way.
  • In social networking software.
  • In a telecommunications network.
  • To locate the sites on the map.

Pseudo Code

function Dijkstra(Graph, source):
  	// The distance from source to the source is set to 0
       	dist[source]  := 0  
  	// Initializations                
    	for each vertex v in Graph:         
        	if v ≠ source
			// Unknown distance function from source to each node set to infinity
               	dist[v] := infinity
			// All nodes initially in Q
           	add v to Q                        
  	// The main loop
   	while Q is not empty:   
	// In the first run-through, this vertex is the source node          
       	v:= vertex in Q with min dist[v] 
          	remove v from Q
 	// Where neighbor u have not yet been removed from Q.
       	for each neighbor u of v:          
           	alt := dist[v] + length(v, u)
 	// A shorter path to u has been found
           	if alt < dist[u]:      
 	// Update distance of u      
               	dist[u]  := alt           
	return dist[]
end function

Pictorial Way Representation

Step 1: Create a weighted graph in which each branch assigns a certain numerical weight. Likewise, a weighted graph is a particular labeled graph in which the labels are numbers (which are positive).

Step 1

Step 2: Pick a starting vertex, and give all other devices infinity path values.

step 2

Step 3: By visiting, update the path length of each vertex.

step 3

Step 4: If the next vertex's path length is smaller than the new path length, do not update it.

step 4

Step 5: Avoid changing the path lengths of previously visited vertices.

step 5

Step 6: We choose the unvisited vertex with the shortest path length after each iteration. As a result, we select 4 before 5.

step 6

Step 7: Take note of how the path length of the rightmost vertex is modified twice.

step 7

Here we choose the unvisited vertex with the shortest path length after each iteration. As a result, we select 6 before 9.

Step 8: Continue until all of the vertices have been visited.

step 8

In the last step, we found the shortest path to travel along the graph.

0--> 0: distance=0

0--> 3: distance=3(both)(0+3)

0--> 5: distance=5(0+3+2)

0--> 4: distance=4(3+1)

0--> 6: distance=9(3+6)

Implementation in Python

# Program to find Paths in Dijkstra’s Shortest Path Algorithm
import sys

# Determine which of the unvisited nodes has to be visited next using this function
def to_be_visited():
  global visited_dist
  v = -10
# Choosing the vertex with the minimum distance
  for index in range(num_of_vertices):
    if visited_dist[index][0] == 0 \
      and (v < 0 or visited_dist[index][1] <= \
      visited_dist[v][1]):
        v = index
  return v

# Creating the graph as an adjacency matrix
'''
vertices = [[0, 1, 1, 0],
            [0, 0, 1, 0],
            [0, 0, 0, 1],
            [0, 0, 0, 0]]
edges =  [[0, 3, 4, 0],
          [0, 0, 0.5, 0],
          [0, 0, 0, 1],
          [0, 0, 0, 0]]
'''
v = int(input('Enter the range of vertices: '))
vertices = []
print('Enter the vertices of the graph: ')
for i in range(v):    
  a =[]
  for j in range(v):  
    a.append(float(input()))
  vertices.append(a)

print('Enter the edges of the graph: ')
edges = []
for i in range(v):    
  a =[]
  for j in range(v):  
    a.append(float(input()))
  edges.append(a)

num_of_vertices = v

# If a vertex has been visited, it is indicated by the first element in the lists inside visited and distance.
# The distance from the source is indicated by the second element of the lists inside the visited and distance.

visited_dist = [[0, 0]]
for i in range(num_of_vertices-1):
  visited_dist.append([0, sys.maxsize])

for vertex in range(num_of_vertices):
   
# Finding the next vertex to be visited.

  to_visit = to_be_visited()
  for neigh_index in range(num_of_vertices):
     
    # We will be calculating the new distance for all unvisited 
    # neighbours of the chosen vertex.
   
    if vertices[to_visit][neigh_index] == 1 and \
     visited_dist[neigh_index][0] == 0:
      new_distance = visited_dist[to_visit][1] \
      + edges[to_visit][neigh_index]
     
     # Updating dist of the neighbor if its current distance is greater than the distance that has just been calculated.
     
      if visited_dist[neigh_index][1] > new_distance:
        visited_dist[neigh_index][1] = new_distance
       
  # Visiting the vertex found earlier.
 
  visited_dist[to_visit][0] = 1

i = 0

# Let us print out the shortest distance from the source to each vertex.

for distance in visited_dist:
  print("The shortest distance of ",chr(ord('a') + i),\
  " from the source vertex a is:",distance[1])
  i = i + 1

Output

Output
Output

Output Explanation:

Output explanation

Time Complexity

The time complexity o the problem “Paths in Dijkstra’s Shortest Path Algorithm” O(e Log V), where ‘e’ is the no. of edges and ‘V’ is the number of vertices.

Space Complexity

The space complexity of the problem "Paths in Dijkstra’s Shortest Path Algorithm" using the above approach is O(V).

Frequently Asked Questions

Which data structure is used in Dijkstra's algorithm?

Because the required operations in Dijkstra's Algorithm match the specialization of a minimum priority queue, the minimum priority queue is the most widely used data structure for implementing Dijkstra's Algorithm.

Does Dijkstra's algorithm always find the shortest path?

Yes, Dijkstra's algorithm always finds the shortest path when all edge costs are positive. It may, however, fail if there are negative edge costs.

Is Dijkstra a DFS or a BFS?

Dijkstra's algorithm is just BFS with a priority queue. The breadth-first search, or BFS algorithm, is used to look for nodes that fulfill a set of criteria in a tree or graph data structure.

Where is the shortest path algorithm used?

There are numerous applications for shortest path algorithms. Shortest path algorithms are used in mapping software such as Google Maps and Apple Maps. Shortest path algorithms are also critical for computer networks such as the Internet.

Does Google Maps use Dijkstra?

Google Maps essentially uses two Graph algorithms – Dijkstra's algorithm and A* algorithm, to calculate the shortest distance from point A ( Source) to point B ( destination).

Conclusion

In this blog, we have learned about the Paths in Dijkstra’s Shortest Path Algorithm. The blog includes programming as well.

If you found this blog has helped you enhance your knowledge, and if you want to learn more, check out our articles like Paths in Dijkstra’s Shortest Path Algorithm below:

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!

Live masterclass