PYTHON

dijkstras python

"""
This implementation takes in a single source node, and returns a dictionary
of the predecessors. The implementation of print path beneath it returns 
the Dijkstra's algorithm shortest path from the source node, to a target node.
"""

class Graph:
    def __init__(self, graph={}):
        self.graph = graph

	def Dijkstra(self, source):
      dist = {}
      pred = {}
      u = source

      unvisited = set()

      for vertex in self.graph.keys():  # Initializations
        dist[vertex] = sys.maxsize
        unvisited.add(vertex)  # All nodes initially in Q
        pred[vertex] = -1

        dist[source] = 0  # Distance from source to source is set to 0

      while len(unvisited) > 0:  # The main loop

        minDistance = sys.maxsize
        minVertex = source
        for vertex in unvisited:
          if dist[vertex] < minDistance:
            minDistance = dist[vertex]
            minVertex = vertex

            u = minVertex
            unvisited.remove(u)

            for neighborEdge in self.graph[u]:
              w = float(neighborEdge[1])
              v = neighborEdge[0]

              newLength = dist[u] + w

              if newLength < dist[v]:
                dist[v] = newLength
                pred[v] = u
		return pred
        
	def printPath(self, pred, source, target):
        path = [target]
        while path[-1] != source:
            predKey = pred.get(target)
            path.append(predKey)
            target = predKey

        path.reverse()
        # print(path)
        return path