Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· OpenAIAi2 WildChat-4.8M (AI2)

Напиши программу поиска кратчайшего пути, где можно выбирать между методами Флойда и…

  1. User

    Напиши программу поиска кратчайшего пути, где можно выбирать между методами Флойда и Данцига.

  2. Assistant
    import numpy as np
    import sys
    
    def initialize_distances(vertices, adjacency_matrix):
        distances = []
        for i in range(vertices):
            row = []
            for j in range(vertices):
                if adjacency_matrix[i][j] == 0:
                    row.append(sys.maxsize)
                else:
                    row.append(adjacency_matrix[i][j])
            distances.append(row)
        return distances
    
    def floyd_warshall(vertices, distances):
        for k in range(vertices):
            for i in range(vertices):
                for j in range(vertices):
                    if distances[i][k] + distances[k][j] < distances[i][j]:
                        distances[i][j] = distances[i][k] + distances[k][j]
        return distances
    
    def dantzig(vertices, distances):
        for k in range(0, vertices-1):
            for i in range(vertices):
                for j in range(vertices):
                    if distances[i][k] + distances[k + 1][j] < distances[i][j]:
                        distances[i][j] = distances[i][k] + distances[k + 1][j]
        return distances
    
    def main():
        print("Enter number of vertices and adjacency matrix:")
        vertices = int(input())
        adjacency_matrix = []
        for _ in range(vertices):
            row = [int(x) for x in input().split()]
            adjacency_matrix.append(row)
    
        distances = initialize_distances(vertices, adjacency_matrix)
    
        print("Choose algorithm:")
        print("1. Floyd-Warshall")
        print("2. Dantzig")
        choice = int(input())
    
        print("Shortest path distances:")
        if choice == 1:
            shortest_paths = floyd_warshall(vertices, distances)
        elif choice == 2:
            shortest_paths = dantzig(vertices, distances)
        else:
            print("Invalid choice.")
            return
    
        for row in shortest_paths:
            print(" ".join(str(x) for x in row))
    
    if __name__ == "__main__":
        main()
    

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

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