A 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 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
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.
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 2: Pick a starting vertex, and give all other devices infinity path values.
Step 3: By visiting, update the path length of each vertex.
Step 4: If the next vertex's path length is smaller than the new path length, do not update it.
Step 5: Avoid changing the path lengths of previously visited vertices.
Step 6: We choose the unvisited vertex with the shortest path length after each iteration. As a result, we select 4 before 5.
Step 7: Take note of how the path length of the rightmost vertex is modified twice.
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.
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
You can also try this code with Online Python Compiler
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:
46+ registered 