Как правильно реализовать алгоритм Дейкстры в Python с применением ООП?

Алгоритм Дейкстры — это алгоритм нахождения кратчайшего пути от одной вершины до всех остальных вершин во взвешенном ориентированном графе. В Python мы можем реализовать этот алгоритм с использованием объектно-ориентированного программирования (ООП) следующим образом:

1. Создайте класс для представления графа. Класс будет содержать методы для добавления вершин и ребер к графу.

class Graph:
    def __init__(self):
        self.vertices = {}

    def add_vertex(self, vertex):
        self.vertices[vertex] = {}

    def add_edge(self, vertex1, vertex2, weight):
        self.vertices[vertex1][vertex2] = weight

2. Создайте класс для реализации алгоритма Дейкстры. Класс будет содержать методы для нахождения кратчайшего пути от одной вершины до всех остальных вершин.

class Dijkstra:
    def __init__(self, graph):
        self.graph = graph

    def find_shortest_path(self, start_vertex):
        distances = {vertex: float('inf') for vertex in self.graph.vertices}
        distances[start_vertex] = 0
        visited = set()

        while len(visited) < len(self.graph.vertices):
            current_vertex = self.find_minimum_distance(distances, visited)
            visited.add(current_vertex)

            for neighbor, weight in self.graph.vertices[current_vertex].items():
                new_distance = distances[current_vertex] + weight
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance

        return distances

    def find_minimum_distance(self, distances, visited):
        min_distance = float('inf')
        min_vertex = None
        for vertex, distance in distances.items():
            if distance < min_distance and vertex not in visited:
                min_distance = distance
                min_vertex = vertex
        return min_vertex

3. Продемонстрируйте использование классов для решения конкретной задачи:

# Создание графа
graph = Graph()
graph.add_vertex('A')
graph.add_vertex('B')
graph.add_vertex('C')
graph.add_vertex('D')

graph.add_edge('A', 'B', 5)
graph.add_edge('A', 'C', 2)
graph.add_edge('B', 'C', 1)
graph.add_edge('B', 'D', 6)
graph.add_edge('C', 'D', 4)

# Решение задачи
dijkstra = Dijkstra(graph)
distances = dijkstra.find_shortest_path('A')

# Вывод результатов
for vertex, distance in distances.items():
    print(f"Кратчайшее расстояние от A до {vertex}: {distance}")

Вывод программы будет следующим:

Кратчайшее расстояние от A до A: 0
Кратчайшее расстояние от A до B: 5
Кратчайшее расстояние от A до C: 2
Кратчайшее расстояние от A до D: 6

Таким образом, алгоритм Дейкстры успешно реализован с помощью объектно-ориентированного программирования в Python.