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` возвращает матрицу расстояний между всеми парами вершин.

    No Comments

Comments are closed.