Dijkstra’s Shortest Path Algorithm

The Dijkstra’s Shortest Path algorithm is a greedy algorithm which is used for finding the shortest path between nodes in a graph. This algorithm finds the shortest path between the two nodes but it can be used for finding the shortest paths from a single node to all other nodes by iterating the algorithm for more than once (Total number of nodes – 1).

Working of Dijkstra’s Shortest Path algorithm

Dijkstra’s Shortest Path algorithm is working on the greedy approach. In this shortest path tree with given source as a root is generated. And every step of the algorithm finds the vertex has a minimum distance from the source.
It uses the property in the opposite direction that if the shortest path between vertices A and C that is A -> C and B -> C is the subpath in A -> C then B -> C is also the shortest path between vertices B and C.

Example of Dijkstra’s algorithm

Greedy algorithm approach is used for finding the shortest path between nodes in a graph.
Below is the example of Dijkstra’s algorithm with input- output constraint and the solution for the example.

Input and Output of the Example

Given the weighted graph G, and the task is used to find the shortest path between nodes.

Solution:

Stepwise Solution of the Problem Example using Dijkstra’s Shortest Path Algorithm

Step 1: Start with the given weighted graph

Step 2: Pick the starting vertex and assign infinity path values to all other vertices.

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

Step 4: If the path length of adjacent vertex is less than new path don’t update it and avoid updating path lengths of already visited vertices.

Step 5: After each iteration, pick unvisited with least path and repeat until all vertices have been visited.

Step 6: Return the solution

Pseudocode for Dijkstra’s Shortest Path algorithm

Here’s Pseudocode for finding the shortest path between the nodes in a graph using greedy algorithm approach.

Dijkstra(Graph, source):
    // Initializations
   for each vertex v in Graph:     
        // Unknown distance function from source to
        //each node set to infinity
        dist[v]  <- infinity    

         // All nodes initially in Q
         add v to Q                        

    // Distance from source to source is set to 0
    dist[source]  := 0                     

    while Q is not empty:                  
        v <- vertex  min dist[v] from Q 

        remove v 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[]

Implementation of Dijkstra’s Shortest Path Algorithm in Python

# Dijkstra's Algorithm in Python
import sys

# Function to find which vertex is to be visited next
def next_to_visited():
    global visited
    v = -10
    for index in range(num_of_vertices):
        if visited[index][0] == 0 and (v < 0 or visited[index][1] <= visited[v][1]):
            v = index
    return v

# Function to find the shortest path between nodes in a graph   
def dijkstra():
    for vertex in range(num_of_vertices):

        # Find next vertex to be visited
        visit = next_to_visited()

        for index in range(num_of_vertices):

            # Updating new distances
            if vertices[visit][index] == 1 and visited[index][0] == 0:
                new_distance = visited[visit][1] + edges[visit][index]
                if visited[index][1] > new_distance:
                    visited[index][1] = new_distance

            visited[visit][0] = 1

# Printing the distance
def print_dist():
    i = 0
    for distance in visited[1:]:
        print("Distance from S ->", chr(ord('A')+i), ":",distance[1])
        i = i + 1

# Driver Code
# Providing the graph
# 2D array to represnt the vertex structure
vertices = [[0, 1, 1, 1],
            [1, 0, 1, 0],
            [1, 1, 0, 1],
            [1, 0, 1, 0]]

# 2D array to represnt the edge structure
edges = [[0, 1, 2, 5],
        [1, 0, 2, 0],
        [2, 2, 0, 4],
        [5, 0, 4, 0]]

# calculate Number of vertices
num_of_vertices = len(vertices[0])

# store the visited edge and vertex
visited = [[0, 0]]
for i in range(num_of_vertices-1):
    visited.append([0, sys.maxsize])

# Function calling 
dijkstra()
print_dist()