import heapq
def shortest_path(graph, start, end):
# Create a priority queue to store the vertices
heap = [(0, start)]
visited = set()
while heap:
(cost, current) = heapq.heappop(heap)
if current in visited:
continue
visited.add(current)
if current == end:
return cost
for (neighbour, weight) in graph[current].items():
if neighbour not in visited:
heapq.heappush(heap, (cost + weight, neighbour))
return float("inf")
# Example graph representation
graph = {
"A": {"B": 1, "C": 4},
"B": {"A": 1, "C": 2, "D": 5},
"C": {"A": 4, "B": 2, "D": 1},
"D": {"B": 5, "C": 1}
}
print(shortest_path(graph, "A", "D")) # Output: 3