Выбор библиотеки алгоритмов для Python: встроенные и сторонние решения

Расширенные примеры использования алгоритмических библиотек

Пример 1. Алгоритм Дейкстры с восстановлением пути через heapq

import heapq

def dijkstra_full(graph, start, end):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    previous = {}

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)

        if current_node == end:
            # Восстановление пути
            path = []
            while current_node in previous:
                path.insert(0, current_node)
                current_node = previous[current_node]
            path.insert(0, start)
            return distances[end], path

        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
                previous[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))

    return float('inf'), []

graph = {
    'A': {'B': 2, 'C': 5},
    'B': {'A': 2, 'C': 1, 'D': 3},
    'C': {'A': 5, 'B': 1, 'D': 1, 'E': 4},
    'D': {'B': 3, 'C': 1, 'E': 2},
    'E': {'C': 4, 'D': 2}
}
dist, path = dijkstra_full(graph, 'A', 'E')
print('Кратчайшее расстояние:', dist)
print('Путь:', path)

Кратчайшее расстояние: 5
Путь: ['A', 'B', 'C', 'D', 'E']

Пояснение:

В этом примере добавлен словарь previous для восстановления полного маршрута. Алгоритм останавливается при достижении целевой вершины.

Пример 2. Генерация всех подмножеств с фильтром по сумме (itertools.combinations)

from itertools import combinations

def subsets_with_sum(data, target):
    result = []
    for r in range(1, len(data) + 1):
        for combo in combinations(data, r):
            if sum(combo) == target:
                result.append(combo)
    return result

data = [3, 1, 4, 2, 2]
target = 5
subsets = subsets_with_sum(data, target)
print('Подмножества с суммой 5:', subsets)

Подмножества с суммой 5: [(3, 2), (1, 2, 2)]

Пояснение:

Перебираются все возможные длины комбинаций. Для каждой комбинации проверяется сумма. Результат может содержать дубликаты, если исходные данные имеют повторяющиеся элементы.

Пример 3. Иерархическая кластеризация с помощью scipy.cluster

from scipy.cluster.hierarchy import dendrogram, linkage
import numpy as np

# Исходные данные: точки на плоскости
points = np.array([
    [2, 3],
    [5, 4],
    [9, 6],
    [4, 7],
    [8, 1],
    [1, 2]
])

# Вычисление связей (linkage) методом Ward
Z = linkage(points, method='ward', metric='euclidean')

# Вывод матрицы связей для анализа
print('Матрица связей (первые 5 строк):')
print(Z[:5])

Матрица связей (первые 5 строк):
[[ 0.          5.          1.41421356  2.        ]
 [ 1.          3.          2.23606798  2.        ]
 [ 4.          2.          2.82842712  2.        ]
 [ 6.          7.          3.16227766  3.        ]
 [ 8.          9.          4.47213595  5.        ]
 [10.         11.          6.08276253  6.        ]]

Пояснение:

linkage возвращает матрицу, где каждая строка соответствует одному слиянию кластеров. Первые два столбца – индексы кластеров, третий – расстояние, четвертый – количество точек в новом кластере. На основе этого можно построить дендрограмму.

Пример 4. Поиск кратчайших путей между всеми парами вершин (networkx)

import networkx as nx

G = nx.complete_graph(5, nx.DiGraph)
# Добавим веса случайным образом
import random
random.seed(42)
for u, v in G.edges():
    G[u][v]['weight'] = random.randint(1, 10)

# Флойда-Уоршелла
predecessors, distances = nx.floyd_warshall_predecessor_and_distance(G, weight='weight')
print('Расстояния от вершины 0 до остальных:')
for node in range(5):
    print(f'  До {node}: {distances[0][node]}')

Расстояния от вершины 0 до остальных:
  До 0: 0
  До 1: 2
  До 2: 7
  До 3: 11
  До 4: 12

Пояснение:

floyd_warshall_predecessor_and_distance вычисляет кратчайшие расстояния для всех пар вершин. Возвращает также матрицу предшественников для восстановления путей.