import heapq

class Graph:
    def __init__(self):
        self.graph = {}              # adjacency list
        self.edge_lengths = {}       # edge length dictionary

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []
        else:
            print(f"Vertex {vertex} already exists.")

    def add_edge(self, vertex1, vertex2, length: float):
        if vertex1 in self.graph and vertex2 in self.graph:
            self.graph[vertex1].append(vertex2)
            self.graph[vertex2].append(vertex1)
            # Store edge length using a frozenset to avoid duplicates
            self.edge_lengths[frozenset([vertex1, vertex2])] = length
        else:
            print("One or both vertices not found.")

    def display(self):
        print("Adjacency List:")
        for vertex in self.graph:
            print(f'{vertex}: {self.graph[vertex]}')
        print("\nEdge Lengths:")
        for edge, length in self.edge_lengths.items():
            v1, v2 = tuple(edge)
            print(f'{v1} - {v2}: {length}')
            

    def dijkstra(self, start, end):
        distances = {vertex: float('inf') for vertex in self.graph}
        distances[start] = 0
        previous = {vertex: None for vertex in self.graph}
        queue = [(0, start)]

        while queue:
            current_distance, current_vertex = heapq.heappop(queue)

            if current_vertex == end:
                break

            for neighbor in self.graph[current_vertex]:
                edge = frozenset([current_vertex, neighbor])
                weight = self.edge_lengths.get(edge, float('inf'))
                distance = current_distance + weight

                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    previous[neighbor] = current_vertex
                    heapq.heappush(queue, (distance, neighbor))

        # Reconstruct path
        path = []
        current = end
        while current:
            path.insert(0, current)
            current = previous[current]

        print(f"Shortest path from {start} to {end}: {' -> '.join(path)} with length {distances[end]}")
            
# Example usage
g = Graph()

# City node abbreviations
A = "San Tan Valley"
B = "Phoenix"
C = "Globe"
D = "Mesa"
E = "Florence"

# Adding nodes to graph
g.add_vertex(A)
g.add_vertex(B)
g.add_vertex(C)
g.add_vertex(D)
g.add_vertex(E)

# Adding edges to graph
g.add_edge(A, B, 34)
g.add_edge(A, C, 47)
g.add_edge(B, D, 18.8)
g.add_edge(C, D, 13)
g.add_edge(B, E, 63)

g.display()
g.dijkstra(A, D)