1if __name__ == '__main__':
2    # Python code for finding the shortest path
3    from collections import defaultdict, deque
4
5    class Graph:
6        def __init__(self):
7            self.adj_list = defaultdict(list)
8
9        def add_edge(self, source, destination, weight):
10            self.adj_list[source].append((destination, weight))
11
12        def shortest_path(self, start, end):
13            distances = {vertex: float('inf') for vertex in self.adj_list}
14            distances[start] = 0
15            previous_vertices = {}
16            queue = deque([start])
17
18            while queue:
19                current_vertex = queue.popleft()
20
21                for neighbor, edge_weight in self.adj_list[current_vertex]:
22                    weight = distances[current_vertex] + edge_weight
23
24                    if weight < distances[neighbor]:
25                        distances[neighbor] = weight
26                        previous_vertices[neighbor] = current_vertex
27                        queue.append(neighbor)
28
29            path = []
30            current_vertex = end
31
32            while current_vertex != start:
33                path.append(current_vertex)
34                current_vertex = previous_vertices[current_vertex]
35
36            path.append(start)
37            path.reverse()
38
39            return path
40
41    # Create a graph
42    g = Graph()
43
44    # Add edges to the graph
45    g.add_edge('A', 'B', 5)
46    g.add_edge('A', 'C', 3)
47    g.add_edge('B', 'D', 2)
48    g.add_edge('C', 'D', 1)
49    g.add_edge('C', 'E', 6)
50    g.add_edge('D', 'E', 4)
51    g.add_edge('D', 'F', 8)
52    g.add_edge('E', 'F', 5)
53
54    # Find the shortest path between two nodes
55    shortest_path = g.shortest_path('A', 'F')
56
57    print('Shortest Path:')
58    print(' -> '.join(shortest_path))