Discover the Power of Dijkstra's Algorithm: Python Edition.

Shortest paths between nodes use case.


Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph. The original algorithm version is used to find the shortest path between two given nodes. The most commonly used variant sets a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, constructing a shortest-path tree (SPT).

Dijkstra's Algorithm.
Dijkstra's Algorithm meme.

Python Knowledge Base: Make coding great again.
- Updated: 2024-07-23 by Andrey BRATUS, Senior Data Analyst.




    The algorithm uses a greedy approach, trying to find the next best solution hoping that the end result is the best solution for the whole problem.

    The main steps for Dijkstra's algorithm are:
    - Set the ending vertex distance to zero. Assign this vertex as current. - Find all vertices leading to the current vertex and calculate their distances to the end. - Mark the current vertex as visited. - Set the vertex with the smallest distance as current, repeat from step 2.



  1. Dijkstra's Algorithm Python code:


  2. 
    class Graph():
     
        def __init__(self, vertices):
            self.V = vertices
            self.graph = [[0 for column in range(vertices)]
                          for row in range(vertices)]
     
        def printSolution(self, dist):
            print("Vertex \t Distance from Source:")
            for node in range(self.V):
                print(node, "\t\t", dist[node])
     
        # find the vertex with minimum distance value
        def minDistance(self, dist, sptSet):
     
           
            min = 1e7
     
            # Search not nearest vertex
            for v in range(self.V):
                if dist[v] < min and sptSet[v] == False:
                    min = dist[v]
                    min_index = v
     
            return min_index
     
        def Dijkstra(self, src):
     
            dist = [1e7] * self.V
            dist[src] = 0
            sptSet = [False] * self.V
     
            for cout in range(self.V):
     
                # Pick the minimum distance vertex
                u = self.minDistance(dist, sptSet)
     
                # Put it in the shortest path tree
                sptSet[u] = True
     
                # Update dist value of the adjacent vertices
                for v in range(self.V):
                    if (self.graph[u][v] > 0 and
                       sptSet[v] == False and
                       dist[v] > dist[u] + self.graph[u][v]):
                        dist[v] = dist[u] + self.graph[u][v]
     
            self.printSolution(dist)
     
    # Driver program
    g = Graph(7)
    
    g.graph = [[0, 0, 1, 2, 0, 0, 0],
             [0, 0, 2, 0, 0, 3, 0],
             [1, 2, 0, 1, 3, 0, 0],
             [2, 0, 1, 0, 0, 0, 1],
             [0, 0, 3, 0, 0, 2, 0],
             [0, 3, 0, 0, 2, 0, 1],
             [0, 0, 0, 1, 0, 1, 0]]
     
    g.Dijkstra(0)
    
  3. Dijkstra's Algorithm code output:


  4. Dijkstra's output.



See also related topics: