# 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
         [6, 11],
         [7, 8],
         [9]]

_ = None
#           0  1  2  3  4  5  6  7  8  9 10 11
weights = [[_, 1, _, 4, _, _, _, _, _, _, _, _], # 0
           [1, _, 1, 3, _, _, _, _, _, _, _, _], # 1
           [_, 1, _, _, 3, 8, _, _, _, _, _, _], # 2
           [4, 3, _, _, _, 2, 2, _, _, _, _, _], # 3
           [_, _, 3, _, _, _, _, 1, _, _, _, _], # 4
           [_, _, 8, 2, _, _, _, 2, 7, _, _, _], # 5
           [_, _, _, 2, _, _, _, _, 3, 2, _, _], # 6
           [_, _, _, _, 1, 2, _, _, _, _, 3, _], # 7
           [_, _, _, _, _, 7, 3, _, _, _, 2, _], # 8
           [_, _, _, _, _, _, 2, _, _, _, _, 1], # 9
           [_, _, _, _, _, _, _, 3, 2, _, _, _], #10
           [_, _, _, _, _, _, _, _, _, 1, _, _]] #11

dist, prec = dijkstra(graph, weights, source=0)

print(dist[10])
print("%i %i %i %i %i %i" % (10, prec[10], prec[prec[10]], prec[prec[prec[10]]],
      prec[prec[prec[prec[10]]]], prec[prec[prec[prec[prec[10]]]]]))

sparse_graph = listlist_and_matrix_to_listdict(weights)


# provides the same behavior


# 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

         [6, 11],
         [7, 8],
         [9]]

_ = None
#           0  1  2  3  4  5  6  7  8  9 10 11
weights = [[_, 1, _, 4, _, _, _, _, _, _, _, _], # 0
           [1, _, 1, 3, _, _, _, _, _, _, _, _], # 1
           [_, 1, _, _, 3, 8, _, _, _, _, _, _], # 2
           [4, 3, _, _, _, 2, 2, _, _, _, _, _], # 3
           [_, _, 3, _, _, _, _, 1, _, _, _, _], # 4
           [_, _, 8, 2, _, _, _, 2, 7, _, _, _], # 5
           [_, _, _, 2, _, _, _, _, 3, 2, _, _], # 6
           [_, _, _, _, 1, 2, _, _, _, _, 3, _], # 7
           [_, _, _, _, _, 7, 3, _, _, _, 2, _], # 8
           [_, _, _, _, _, _, 2, _, _, _, _, 1], # 9
           [_, _, _, _, _, _, _, 3, 2, _, _, _], #10
           [_, _, _, _, _, _, _, _, _, 1, _, _]] #11

dist, prec = dijkstra(graph, weights, source=0)

print(dist[10])
print("%i %i %i %i %i %i" % (10, prec[10], prec[prec[10]], prec[prec[prec[10]]],
      prec[prec[prec[prec[10]]]], prec[prec[prec[prec[prec[10]]]]]))

sparse_graph = listlist_and_matrix_to_listdict(weights)


# provides the same behavior


dist, prec = dijkstra(graph, weights, source=0)