Dijkstra Algorithm

# Python 2.7.X Implementation For Dijksta Algo

# Importing Sys Lib just to include maxInt function
# That returns the highest Integer that machine can hold
import sys
import time
from os import system
# Creating a main class to hold all functions


class Dijksta:
    # Creating Default constructer to init our graph and object
    # Vertices/Number of nodes in our graph
    def __init__(self, Vertices):
        # Setting value of vertices to init out graph
        self.vertices = Vertices
        # Makeing our defaut graph to hold value 0 initallly
        self.graph = [[0 for column in range(Vertices)]
                      for row in range(Vertices)]

    # Function to add nodes when you dont want to supply Matrix form
    def addNode(self, srcNode, dstNode, weight):
        self.graph[srcNode][dstNode] = weight
        self.graph[dstNode][srcNode] = weight

    # A printing function that will print all distances
    def printDistance(self, DistArray):
        print "Node \t Distance"
        for node in range(self.vertices):
            print "{} \t {}".format(node, DistArray[node])
        print "Shortest Path For All Nodes"
        # Commented Below will be used later to see how this works
        # time.sleep(3)
        # system("cls")

    # A function that returns the minimum distance index from the given set of vertex
    # wich in not included in shortest path tree set
    def minDistance(self, dist, sptSet):
        # Var which stores minimum distance init let us consider this value as infinite
        minDis = sys.maxint
        for v in range(self.vertices):
            if dist[v] < minDis and sptSet[v] == False:
                minDis = dist[v]
                min_dist_index = v
        return min_dist_index

    # Fucntion to implement dijkstra algo
    # src is the source node
    def calculateDijkstra(self, src):
        """
        Paramater Src : Source Node Value
        """
        # Initlize all distance as infinte first and make array equal to
        # Number of vertices/nodes
        dist = [sys.maxint] * self.vertices
        # Distance form the souce node is always equal to 0
        dist[src] = 0
        # Shortest Path Tree Set i.e this array will hold the true if
        # the value of shortest distance form src node to node i is finalized
        sptSet = [False] * self.vertices

        # Now Itterate over the graph
        for _ in range(self.vertices):
            # Now let us pick the shortest distance "index" from the dist array
            # The shortest distance in first ittration is always 0 as Distance from Source Node is 0
            # And it is not yet processed hence it is also not included in sptSet
            # We are going to use our utility function here
            # SDI = Shortest Distance Index
            SDI = self.minDistance(dist, sptSet)

            # As we have found the shortest distance index we are going to
            # update sptSet array to state it is the finalized shortest distance
            sptSet[SDI] = True

            # Now we are going to update the distances in Dist Array
            # Only if
            # 1. It is connected to some other node i.e distance to other node is not 0
            #    if it is 0 then node is not connected with each other
            # 2. The shortest distance is not yet finalized ie index value in sptSet is not True
            #    if it finalized no need to update value
            # 3. And if its value in dist array is more then previous Min Distance plus the disstance
            #    to the next connected node
            # Repeat this for all the vertex connected to the current node ie node with minimum distance
            for noVertex in range(self.vertices):
                if self.graph[SDI][noVertex] > 0 and sptSet[noVertex] == False and dist[noVertex] > dist[SDI] + self.graph[SDI][noVertex]:
                    # Update all the min distance values exit loop 2
                    dist[noVertex] = dist[SDI] + self.graph[SDI][noVertex]
                # Exit loop
            time.sleep(1)
            print dist
            print sptSet
        # Now let us print all the minimum distances in dist array
        self.printDistance(dist)


# Now let's fire the functions
Graph = Dijksta(9)
Graph.graph = [
    [0, 4, 0, 0, 0, 0, 0, 8, 0],
    [4, 0, 8, 0, 0, 0, 0, 11, 0],
    [0, 8, 0, 7, 0, 4, 0, 0, 2],
    [0, 0, 7, 0, 9, 14, 0, 0, 0],
    [0, 0, 0, 9, 0, 10, 0, 0, 0],
    [0, 0, 4, 14, 10, 0, 2, 0, 0],
    [0, 0, 0, 0, 0, 2, 0, 1, 6],
    [8, 11, 0, 0, 0, 0, 1, 0, 7],
    [0, 0, 2, 0, 0, 0, 6, 7, 0]
]
Graph.calculateDijkstra(0)