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

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.

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)