dijkstras.py

import heapq

class Graph():
    def __init__(self, g):
        self.g = g

    def dijkstras(self, source):
        distances = { vertex: float('inf') for vertex in self.g }
        distances[source] = 0

        entry_lookup = {}
        priority_queue = []

        for vertex, distance in distances.items():
            entry = [distance, vertex]
            entry_lookup[vertex] = entry
            heapq.heappush(priority_queue, entry)

        while priority_queue:
            dist, v = heapq.heappop(priority_queue)

            for neighbor, neighbor_distance in self.g[v].items():
                distance = distances[v] + neighbor_distance
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    entry_lookup[neighbor][0] = distance

        return distances
                
g = Graph({
    'U': {'V': 2, 'W': 5, 'X': 1},
    'V': {'U': 2, 'X': 2, 'W': 3},
    'W': {'V': 3, 'U': 5, 'X': 3, 'Y': 1, 'Z': 5},
    'X': {'U': 1, 'V': 2, 'W': 3, 'Y': 1},
    'Y': {'X': 1, 'W': 1, 'Z': 1},
    'Z': {'W': 5, 'Y': 1},
})
print(g.dijkstras('X'))
# {'U': 1, 'W': 2, 'V': 2, 'Y': 1, 'X': 0, 'Z': 2}

class Graph(object):
    def __init__(self, g, v):
        self.v = v
        self.g = g

    def dijkstras(self, src):
        dist = [float("inf")] * self.v
        dist[src] = 0
        visited = [False] * self.v

        for i in range(self.v):
            u = self.min_distance(dist, visited)

            visited[u] = True

            for v in range(self.v):
                if self.g[u][v] != 0 and visited[v] == False and dist[v] > dist[u] + self.g[u][v]:
                    dist[v] = dist[u] + self.g[u][v]

        return dist

    def min_distance(self, dist, visited):
        min = float("inf")

        for v in range(self.v):
            if dist[v] < min and visited[v] == False:
                min = dist[v]
                min_index = v
        return min_index

g = 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] 
          ], 9)
print(g.dijkstra(0))
# [0, 4, 12, 19, 21, 11, 9, 8, 14]