Resolved: The closest path between two points in terms of time

from collections import defaultdict


class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def printAllPathsUtil(self, u, d, visited, path):
        visited[u] = True
        path.append(u)

        if u == d:
            print(path)
        else:
            for i in self.graph[u]:
                if visited[i] == False:
                    self.printAllPathsUtil(i, d, visited, path)

        path.pop()
        visited[u] = False

    def printAllPaths(self, s, d):
        visited = [False] * (self.V)
        path = []
        self.printAllPathsUtil(s, d, visited, path)


n = int(input())

adjacency_matrix = []
for i in range(n):
    row = []
    for j in range(n):
        row.append(0)
    adjacency_matrix.append(row)

for i in range(len(adjacency_matrix)):
    for j in range(len(adjacency_matrix[0])):
        adjacency_matrix[i][j] = int(input())

s = int(input())

d = int(input())

pos = [(count1, count2) for count1, lst in enumerate(adjacency_matrix) for count2, num in enumerate(lst) if num != 0]

g = Graph(n)

for i in pos:
    g.addEdge(*i)

print("Following are all different paths from % s to % d :" % (s, d))
g.printAllPaths(s, d)

class Graph:
    def __init__(self, vertices):
        self.v = vertices
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def _find_all_paths(self, u, d, visited, path, paths):
        visited[u] = True
        path.append(u)

        if u == d:
            paths.append(path[:])
        else:
            for i in self.graph[u]:
                if not visited[i]:
                    self._find_all_paths(i, d, visited, path, paths)

        path.pop()
        visited[u] = False

    def find_all_paths(self, s, d):
        paths = []
        self._find_all_paths(s, d, [False] * self.v, [], paths)
        return paths

>>> adjacency_matrix = [
...     [0, 2, 0, 1, 0, 0, 0],
...     [0, 0, 0, 3, 9, 0, 0],
...     [4, 0, 0, 0, 0, 5, 0],
...     [0, 0, 2, 0, 2, 8, 4],
...     [0, 0, 0, 0, 0, 0, 6],
...     [0, 0, 0, 0, 0, 0, 0],
...     [0, 0, 0, 0, 0, 1, 0]
... ]
>>> g = Graph(len(adjacency_matrix))
>>> for i, lst in enumerate(adjacency_matrix):
...     for j, num in enumerate(lst):
...         if num:
...             g.add_edge(i, j)
...
>>> paths = g.find_all_paths(0, 6)
>>> paths
[[0, 1, 3, 4, 6], [0, 1, 3, 6], [0, 1, 4, 6], [0, 3, 4, 6], [0, 3, 6]]
>>> min(paths, key=len)
[0, 3, 6]

class Graph:
    def __init__(self, adj_matrix):
        self.v = len(adj_matrix)
        self.graph = defaultdict(list)

        for i, lst in enumerate(adj_matrix):
            for j, num in enumerate(lst):
                if num:
                    self.graph[i].append((j, num))

    def _find_all_paths(self, u, d, visited, path, length, paths):
        visited[u] = True
        path.append(u)

        if u == d:
            paths.append((path[:], length))
        else:
            for i, dist in self.graph[u]:
                if not visited[i]:
                    self._find_all_paths(i, d, visited, path, length + dist, paths)

        path.pop()
        visited[u] = False

    def find_all_paths(self, s, d):
        paths = []
        self._find_all_paths(s, d, [False] * self.v, [], 0, paths)
        return paths

>>> g = Graph(adjacency_matrix)
>>> paths = g.find_all_paths(0, 6)
>>> paths
[([0, 1, 3, 4, 6], 13),
 ([0, 1, 3, 6], 9),
 ([0, 1, 4, 6], 17),
 ([0, 3, 4, 6], 9),
 ([0, 3, 6], 5)]
>>> from operator import itemgetter
>>> min(paths, key=itemgetter(1))
([0, 3, 6], 5)