from collections import defaultdict

moves = ((-1, 0), (0, -1), (0, 1), (1, 0))


def add_edge(graph, a, b):
    graph[a].add(b)
    graph[b].add(a)


def create_graph(row, col, labyrinth):
    graph = defaultdict(set)
    for i in range(row):
        for j in range(col):
            for new_row, new_col in allowed_moves(i, j, row, col, labyrinth):
                add_edge(graph, (i, j), (new_row, new_col))

    print("Graph:")

    answer = defaultdict()
    for key in graph:
        points = []
        for point in graph[key]:
            points.append(point[0] * col + point[1])
        answer[key[0] * col + key[1]] = sorted(points)

    count = 0
    for key in sorted(answer):
        while key != count:
            print(count, "- None")
            count += 1
        print("%s - %s " % (key, str(answer[key]).replace("[", "").replace("]", "").replace(",", "")))
        count += 1
    while count < row_size*col_size:
        print(count, "- None")
        count += 1

    return graph


def allowed_moves(x, y, row, col, labyrinth):
    if labyrinth[x][y] != "#":
        for row_offset, col_offset in moves:
            new_row, new_col = x + row_offset, y + col_offset
            if 0 <= new_row < row and 0 <= new_col < col and labyrinth[new_row][new_col] != '#':
                yield new_row, new_col




# for adjacency matrix representation of the graph
import sys

class Graph:

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)] for row in range(vertices)]

    def print_result(self, dist):
        print("Vertex tDistance from Source")
        for node in range(self.V):
            print(node, "t", dist[node])

    # A utility function to find the vertex with minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def min_distance(self, dist, sptSet):

        # Initilaize minimum distance for next node
        min = sys.maxsize

        # Search not nearest vertex not in the shortest path tree
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    def dijkstra(self, src):

        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for vertex in range(self.V):

            # Pick the minimum distance vertex from the set of vertices not yet processed.
            u = self.min_distance(dist, sptSet)

            # Put the minimum distance vertex in the shotest path tree
            sptSet[u] = True

            # Update dist value of the adjacent vertices of the picked vertex only if the current
            # distance is greater than new distance and the vertex in not in the shotest path tree
            for v in range(self.V):
                if self.graph[u][v] > 0 and sptSet[v] == False and dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        self.print_result(dist)


g = Graph(9)
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]
           ]

g.dijkstra(0)