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