import sys

class ShortestPathAnd2ndShortestDijkstras:

    NO_PARENT = -1	
    path = []; #nodes in the shortest path
    allDists = set(); #list of shortest distance

    #use Dijkstra’s Shortest Path Algorithm, O(n^2) Space O(n)
    def shortestPath(self, adjacencyMatrix, src, dest) : 
        n = len(adjacencyMatrix[0]) 
        shortest = {}
        visited = {}
        parents = {}
        for v in range(0, n, 1)  :
            shortest[v] =  sys.maxsize; 
            visited[v] = False
        shortest[src] = 0; 
        parents[src] = self.NO_PARENT; 
        for i in range(1, n, 1) : 
            pre = -1; 
            min =  sys.maxsize; 
            for v in range(0, n, 1) : 
                if visited[v]==False and shortest[v] < min : 
                    pre = v; 
                    min = shortest[v]; 
            if pre == -1:
                return
            visited[pre] = True; 
            for v in range(0, n, 1)  : 
                dist = adjacencyMatrix[pre][v];                  
                if dist > 0 and ((min + dist) < shortest[v]) :   
                    parents[v] = pre
                    shortest[v] = min + dist 
        self.allDists.add(shortest[dest])
        self.addPath(dest, parents); 
    

    #utility func to add nodes in the path recursively
    def addPath(self, i, parents) : 	
        if (i == self.NO_PARENT) :
            return  	
        self.addPath(parents[i], parents)             
        self.path.append(i) 

    #get 2nd shortest by removing each edge in shortest and compare  
    def find2ndShortest(self, adjacencyMatrix, src, dest) : 
        #store previous vertex's data  	
        preV = -1
        preS = -1 
        preD = -1 
        mylist = list(self.path)       
        for i in range(0, len(mylist)-1, 1) :
            #get source and destination for each path in shortest path
            s = mylist[i]
            d = mylist[i + 1]
            #resume the previous path 
            if (preV != -1) :
                adjacencyMatrix[preS][preD] = preV
                adjacencyMatrix[preD][preS] = preV       
            #record the previous data for recovery
            preV = adjacencyMatrix[s][d]
            preS = s
            preD = d
            #remove this path
            adjacencyMatrix[s][d] = 0
            adjacencyMatrix[d][s] = 0
            #re-calculate
            self.shortestPath(adjacencyMatrix, src, dest)
    

adjacencyMatrix = [
    [ 0, 1, 0, 1],
    [ 1, 0, 1, 4],
    [ 0, 1, 0, 0],
    [ 1, 4, 0, 0]
]
src = 2
dest = 3

myobj = ShortestPathAnd2ndShortestDijkstras()
myobj.shortestPath(adjacencyMatrix, src, dest); 
print("shortest path: ")       
print(myobj.path)

myobj.find2ndShortest(adjacencyMatrix, src, dest); 
print("shortest distances: ")
print(myobj.allDists)

mylist = list(myobj.allDists); 
print("Shortest distance: " + str(mylist[0]))
print("2nd shortest distance: " + str(mylist[1]))