Кратчайший путь в графе Python: как его найти с помощью простого кода

    from collections import defaultdict
    import heapq

    def dijkstra(graph, start):
        distances = {node: float('inf') for node in graph}
        distances[start] = 0
        pq = [(0, start)]
        
        while pq:
            distance, current = heapq.heappop(pq)
            
            if distance > distances[current]:
                continue
            
            for neighbor, weight in graph[current].items():
                path = distance + weight
                if path < distances[neighbor]:
                    distances[neighbor] = path
                    heapq.heappush(pq, (path, neighbor))
        
        return distances
    
    # Граф в виде словаря смежности
    graph = {
        'A': {'B': 5, 'C': 3},
        'B': {'A': 5, 'C': 1, 'D': 3},
        'C': {'A': 3, 'B': 1, 'D': 2},
        'D': {'B': 3, 'C': 2}
    }
    
    start_node = 'A'
    shortest_distances = dijkstra(graph, start_node)
    print(shortest_distances)
    

    def bellman_ford(graph, start):
        distances = {node: float('inf') for node in graph}
        distances[start] = 0
        
        for _ in range(len(graph) - 1):
            for node in graph:
                for neighbor, weight in graph[node].items():
                    if distances[node] != float('inf') and distances[node] + weight < distances[neighbor]:
                        distances[neighbor] = distances[node] + weight
        
        return distances
    
    # Граф в виде словаря смежности
    graph = {
        'A': {'B': -1, 'C': 4},
        'B': {'C': 3, 'D': 2, 'E': 2},
        'C': {},
        'D': {'B': 1, 'C': 5},
        'E': {'D': -3}
    }
    
    start_node = 'A'
    shortest_distances = bellman_ford(graph, start_node)
    print(shortest_distances)
    

Как найти кратчайший путь в графе с помощью Python

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

1. Представление графа

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

1.1 Матрица смежности

graph = [
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 0],
    [0, 1, 0, 0]
]
    

В этом примере граф представлен в виде матрицы 4x4. Значение 1 в позиции (i, j) указывает на наличие ребра между вершинами i и j.

1.2 Список смежности

graph = {
    0: [1],
    1: [0, 2, 3],
    2: [1],
    3: [1]
}
    

В этом примере граф представлен в виде словаря, где ключи - это вершины, а значения - списки смежных вершин.

2. Алгоритм поиска кратчайшего пути

Существует несколько алгоритмов для поиска кратчайшего пути в графе, включая алгоритм Дейкстры и алгоритм Беллмана-Форда. В этой статье мы сосредоточимся на алгоритме Дейкстры, который эффективен для поиска кратчайшего пути в неотрицательно взвешенных графах.

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

Алгоритм Дейкстры основан на поиске кратчайшего пути от начальной вершины до каждой другой вершины в графе. Процесс состоит из следующих шагов:

import sys
import heapq

def dijkstra(graph, start):
    distances = {node: sys.maxsize for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    
    while heap:
        current_distance, current_node = heapq.heappop(heap)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    
    return distances
    

В этом примере мы используем модуль sys для представления бесконечной дистанции, а модуль heapq для реализации очереди с приоритетом. Функция dijkstra принимает граф и начальную вершину в качестве параметров и возвращает словарь расстояний от начальной вершины до каждой другой вершины.

3. Пример использования

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

graph = {
    'A': {'B': 2, 'C': 4},
    'B': {'A': 2, 'C': 1, 'D': 3},
    'C': {'A': 4, 'B': 1, 'D': 1},
    'D': {'B': 3, 'C': 1}
}

start = 'A'
distances = dijkstra(graph, start)

print(f"Кратчайшие расстояния от вершины {start}:")
for node, distance in distances.items():
    print(f"{node}: {distance}")
    

Этот пример демонстрирует поиск кратчайших расстояний от вершины "A" до каждой другой вершины в графе. Функция dijkstra возвращает словарь расстояний, который мы выводим на экран.

4. Вывод

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