# Dijkstras algorithm for finding shortest paths in
# WeightedDigraph. Modeled after Sedgewick & Wayne's DijkstraSP,
# available at https://algs4.cs.princeton.edu/
#
# Jesper Larsson, Malmö University, 2018–2020

from VertexPQ import VertexPQ

class Dijkstra:
    def __init__(self, G, s):
        self.__edge_to = [-1] * G.V
        self.__s = s
        self.__q = VertexPQ(G.V)
        self.__q.set_dist(s, 0)
        while self.__q:
            v = self.__q.del_min()
            for e in G.adj(v):
                w = e.to
                if self.__q.get_dist(w) > self.__q.get_dist(v) + e.weight:
                    self.__q.set_dist(w, self.__q.get_dist(v) + e.weight)
                    self.__edge_to[w] = v
                    
    def path_to(self, v):
        if self.__q.get_dist(v) < 0:
            return None
        p = [v]
        while v != self.__s:
            v = self.__edge_to[v]
            p.append(v)
        p.reverse()
        return p

    def has_path_to(self, v):
        return self.__q.get_dist(v) < float('inf')

    def dist_to(self, v):
        return self.__q.get_dist(v)