KAN`ский блог
Мысли вслух…
-
Мар8
Алгоритм Флойда-Уоршелла
Filed under: ChatGPT;Алгоритм Флойда-Уоршелла используется для нахождения кратчайших путей между всеми парами вершин во взвешенном ориентированном графе с положительными или отрицательными весами рёбер. Вот пример его реализации на Python:
INF = float('inf') def floyd_warshall(graph): """ Алгоритм Флойда-Уоршелла для поиска кратчайших путей между всеми парами вершин в графе. :param graph: взвешенный граф в виде матрицы смежности :return: матрица расстояний между всеми парами вершин """ n = len(graph) dist = [[INF] * n for _ in range(n)] # Заполняем матрицу начальными значениями for i in range(n): for j in range(n): dist[i][j] = graph[i][j] # Проходим по всем вершинам и обновляем расстояния for k in range(n): for i in range(n): for j in range(n): if dist[i][k] != INF and dist[k][j] != INF: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) return dist # Пример графа в виде матрицы смежности graph = [ [0, 3, INF, 7], [8, 0, 2, INF], [5, INF, 0, 1], [2, INF, INF, 0] ] # Выполняем алгоритм Флойда-Уоршелла result = floyd_warshall(graph) # Выводим результат print("Матрица кратчайших расстояний между всеми парами вершин:") for row in result: print(row)
Этот код реализует алгоритм Флойда-Уоршелла для нахождения кратчайших путей между всеми парами вершин в графе. Входной параметр `graph` представляет собой взвешенный граф в виде матрицы смежности. Функция `floyd_warshall` возвращает матрицу расстояний между всеми парами вершин.