# Path: tryalgo/dijkstra.py
# def dijkstra(graph, weight, source=0, target=None):
#     """single source shortest paths by Dijkstra
# 
#        :param graph: directed graph in listlist or listdict format
#        :param weight: in matrix format or same listdict graph
#        :assumes: weights are non-negative
#        :param source: source vertex
#        :type source: int
#        :param target: if given, stops once distance to target found
#        :type target: int
# 
#        :returns: distance table, precedence table
#        :complexity: `O(|V| + |E|log|V|)`
#     """
#     n = len(graph)
#     assert all(weight[u][v] >= 0 for u in range(n) for v in graph[u])
#     prec = [None] * n
#     black = [False] * n
#     dist = [float('inf')] * n
#     dist[source] = 0
#     heap = [(0, source)]
#     while heap:
#         dist_node, node = heappop(heap)       # Closest node from source
#         if not black[node]:
#             black[node] = True
#             if node == target:
#                 break
#             for neighbor in graph[node]:
#                 dist_neighbor = dist_node + weight[node][neighbor]
#                 if dist_neighbor < dist[neighbor]:
#                     dist[neighbor] = dist_neighbor
#                     prec[neighbor] = node
#                     heappush(heap, (dist_neighbor, neighbor))
#     return dist, prec
# 
# Path: tryalgo/graph.py
# def listlist_and_matrix_to_listdict(graph, weight=None):
#     """Transforms the weighted adjacency list representation of a graph
#     of type listlist + optional weight matrix
#     into the listdict representation
# 
#     :param graph: in listlist representation
#     :param weight: optional weight matrix
#     :returns: graph in listdict representation
#     :complexity: linear
#     """
#     if weight:
#         return [{v: weight[u][v] for v in graph[u]} for u in range(len(graph))]
#     else:
#         return [{v: None for v in graph[u]} for u in range(len(graph))]


from tryalgo.dijkstra import dijkstra
from tryalgo.graph import listlist_and_matrix_to_listdict
#!/usr/bin/env python3


graph = [[1, 3],
         [0, 2, 3],
         [1, 4, 5],
         [0, 1, 5, 6],

# Path: tryalgo/dijkstra.py
# def dijkstra(graph, weight, source=0, target=None):
#     """single source shortest paths by Dijkstra
# 
#        :param graph: directed graph in listlist or listdict format
#        :param weight: in matrix format or same listdict graph
#        :assumes: weights are non-negative
#        :param source: source vertex
#        :type source: int
#        :param target: if given, stops once distance to target found
#        :type target: int
# 
#        :returns: distance table, precedence table
#        :complexity: `O(|V| + |E|log|V|)`
#     """
#     n = len(graph)
#     assert all(weight[u][v] >= 0 for u in range(n) for v in graph[u])
#     prec = [None] * n
#     black = [False] * n
#     dist = [float('inf')] * n
#     dist[source] = 0
#     heap = [(0, source)]
#     while heap:
#         dist_node, node = heappop(heap)       # Closest node from source
#         if not black[node]:
#             black[node] = True
#             if node == target:
#                 break
#             for neighbor in graph[node]:
#                 dist_neighbor = dist_node + weight[node][neighbor]
#                 if dist_neighbor < dist[neighbor]:
#                     dist[neighbor] = dist_neighbor
#                     prec[neighbor] = node
#                     heappush(heap, (dist_neighbor, neighbor))
#     return dist, prec
# 
# Path: tryalgo/graph.py
# def listlist_and_matrix_to_listdict(graph, weight=None):
#     """Transforms the weighted adjacency list representation of a graph
#     of type listlist + optional weight matrix
#     into the listdict representation
# 
#     :param graph: in listlist representation
#     :param weight: optional weight matrix
#     :returns: graph in listdict representation
#     :complexity: linear
#     """
#     if weight:
#         return [{v: weight[u][v] for v in graph[u]} for u in range(len(graph))]
#     else:
#         return [{v: None for v in graph[u]} for u in range(len(graph))]


# Path: docs/example_dijkstra.py
from tryalgo.dijkstra import dijkstra
from tryalgo.graph import listlist_and_matrix_to_listdict

#!/usr/bin/env python3


graph = [[1, 3],
         [0, 2, 3],
         [1, 4, 5],
         [0, 1, 5, 6],

         [2, 7],