Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· openaiHugging Face Suzhen/CodeChat

Напиши на пайтон метод данцига и метод флойда с возможностью выбора

  1. User

    Напиши на пайтон метод данцига и метод флойда с возможностью выбора

  2. Assistant
    import numpy as np
    
    def dantzig_algorithm(matrix):
        n = len(matrix)
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
        return matrix
    
    def floyd_algorithm(matrix):
        n = len(matrix)
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if matrix[i][k] + matrix[k][j] < matrix[i][j]:
                        matrix[i][j] = matrix[i][k] + matrix[k][j]
        return matrix
    
    def shortest_path(matrix, method='dantzig'):
        available_methods = {
            'dantzig': dantzig_algorithm,
            'floyd': floyd_algorithm,
        }
        
        if method not in available_methods:
            raise ValueError(f'Invalid method. Available methods are: {list(available_methods.keys())}')
        
        return available_methods[method](matrix)
    
    # Example usage:
    matrix = [
        [0, 5, np.inf, 10],
        [np.inf, 0, 3, np.inf],
        [np.inf, np.inf, 0, 1],
        [np.inf, np.inf, np.inf, 0],
    ]
    
    result_dantzig = shortest_path(matrix, method='dantzig')
    result_floyd = shortest_path(matrix, method='floyd')
    
    print("Result using Dantzig's Algorithm:")
    print(np.array(result_dantzig))
    
    print("\nResult using Floyd's Algorithm:")
    print(np.array(result_floyd))
    

    Этот код определяет два метода для нахождения кратчайших путей во взвешенном графе: алгоритм Данцига и алгоритм Флойда. Вы можете выбирать между ними, используя параметр method при вызове функции shortest_path.

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

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.