АЛГОРИТМ ФЛОЙДА УОРШЕЛЛА PYTHON
Алгоритм Флойда-Уоршелла (англ. Floyd-Warshall algorithm) используется для поиска кратчайшего пути в графе между всеми парами вершин. Это алгоритм динамического программирования и имеет сложность O(N^3), где N - количество вершин в графе.
Для реализации алгоритма Флойда-Уоршелла на Python, можно использовать следующий код:
def floyd_warshall(graph): dist = [[float('inf') if i != j else 0 for j in range(len(graph))] for i in range(len(graph))] for i in range(len(graph)): for neighbor, weight in graph[i]: dist[i][neighbor] = weight for k in range(len(graph)): for i in range(len(graph)): for j in range(len(graph)): if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j] return distГде graph - это представление графа в виде списка смежности, где каждый элемент списка представляет собой вершину и ее соседей со значениями весов ребер, например:
graph = [ [(1, 2), (2, 4)], [(0, 2), (2, 1)], [(0, 4), (1, 1)]]Результатом выполнения функции floyd_warshall на таком графе будет матрица расстояний между всеми парами вершин:
[ [0, 2, 3], [2, 0, 1], [3, 1, 0]]Это означает, что кратчайший путь между вершиной 0 и вершиной 1 имеет длину 2, между вершиной 0 и вершиной 2 - 3, между вершиной 1 и вершиной 2 - 1.
Алгоритм Флойда
Алгоритм Флойда для нахождения кратчайших путей между вершинами во взвешенном ориентированном графе.
Идея алгоритма Флойда-Уоршелла
Информатика. Теория графов: Алгоритм Флойда. Центр онлайн-обучения «Фоксфорд»
Парадокс АХИЛЛЕС И ЧЕРЕПАХА. Загадки древности.
Лекція 13. Пошук найкоротшого шляху. Алгоритм Флойда-Уоршелла. Програма мовою С++
Алгоритм Флойда
Алгоритм Флойда
Новые материалы: