Поиск кратчайшего пути в Python: алгоритмы и реализация

Поиск кратчайшего пути — одна из ключевых задач в теории графов, имеющая множество практических применений: от маршрутизации в навигационных системах до искусственного интеллекта в играх. В этой статье мы рассмотрим основные алгоритмы поиска кратчайшего пути и их реализацию на Python.

---

Основные алгоритмы поиска кратчайшего пути

1. Поиск в ширину (BFS)

Когда использовать: Ненагруженные графы (без весов на рёбрах).
Принцип работы: Алгоритм исследует все узлы на текущей глубине перед переходом на следующий уровень. Гарантирует нахождение кратчайшего пути по количеству шагов.
Сложность: O(V + E), где V — вершины, E — рёбра.

2. Алгоритм Дейкстры

Когда использовать: Графы с неотрицательными весами рёбер.
Принцип работы: Использует приоритетную очередь для выбора вершины с минимальным текущим расстоянием.
Сложность: O((V + E) log V) при использовании кучи.

3. Алгоритм A*

Когда использовать: Графы с эвристической информацией (например, координаты в сетке).
Принцип работы: Оптимизирует поиск за счёт эвристической функции, оценивающей расстояние до цели.
Сложность: Зависит от эвристики, но часто эффективнее Дейкстры.

---

Реализация алгоритмов на Python

1. Поиск в ширину (BFS)

from collections import deque

def bfs_shortest_path(graph, start, end):
    queue = deque([[start]])
    visited = set()
    
    while queue:
        path = queue.popleft()
        node = path[-1]
        
        if node == end:
            return path
        if node not in visited:
            visited.add(node)
            for neighbor in graph.get(node, []):
                new_path = list(path)
                new_path.append(neighbor)
                queue.append(new_path)
    
    return None  # Путь не найден

# Пример использования
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(bfs_shortest_path(graph, 'A', 'F'))  # ['A', 'C', 'F']

2. Алгоритм Дейкстры

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        
        if current_dist > distances[current_node]:
            continue
            
        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# Пример использования (взвешенный граф)
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'D': 2, 'E': 5},
    'C': {'F': 3},
    'D': {},
    'E': {'F': 1},
    'F': {}
}

print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 1, 'C': 4, 'D': 3, 'E': 6, 'F': 4}

3. Алгоритм A* (для сетки 2D)

def heuristic(a, b):
    # Манхэттенское расстояние
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star(grid, start, end):
    open_set = []
    heapq.heappush(open_set, (0, start))
    came_from = {}
    g_score = {cell: float('inf') for row in grid for cell in row}
    g_score[start] = 0
    
    while open_set:
        current = heapq.heappop(open_set)[1]
        
        if current == end:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            return path[::-1]
            
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            x, y = current[0] + dx, current[1] + dy
            if 0 <= x < len(grid) and 0 <= y < len(grid[0]):
                neighbor = (x, y)
                tentative_g = g_score[current] + 1
                
                if tentative_g < g_score.get(neighbor, float('inf')):
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g
                    f_score = tentative_g + heuristic(neighbor, end)
                    heapq.heappush(open_set, (f_score, neighbor))
    
    return None  # Путь не найден

# Пример использования (0 - свободная клетка, 1 - препятствие)
grid = [
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0]
]
start = (0, 0)
end = (2, 3)
print(a_star(grid, start, end))  # [(0,0), (0,1), (0,2), (0,3), (1,3), (2,3)]

---

Как выбрать алгоритм?

• BFS: Идеален для сеток или графов без весов.
• Дейкстра: Подходит для взвешенных графов с неотрицательными весами.
• A*: Оптимален для задач с известной эвристикой (например, географические координаты).

---

Заключение

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