Напишите программу, которая вводит из файла весовую матрицу графа, затем вводит с клавиатуры номера начальной и конечной вершин и определяет оптимальный маршрут.

Для решения задачи поиска оптимального маршрута в графе по весовой матрице можно использовать алгоритм Дейкстры. Этот алгоритм позволяет находить кратчайшие пути от одной вершины до всех остальных. Предлагаю вам следующую программу на Python, которая будет выполнять описанные вами шаги.

Программа на Python

import numpy as np
import heapq

def load_weight_matrix(filename):
    """Загрузка весовой матрицы из файла."""
    return np.loadtxt(filename)

def dijkstra(weight_matrix, start):
    """Алгоритм Дейкстры для нахождения кратчайшего пути."""
    n = weight_matrix.shape[0]
    distances = [float('inf')] * n
    distances[start] = 0
    priority_queue = [(0, start)]  # (расстояние, вершина)
    
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        # Проверка, если найденное расстояние больше уже известного.
        if current_distance > distances[current_vertex]:
            continue
        
        for neighbor in range(n):
            weight = weight_matrix[current_vertex][neighbor]
            if weight > 0:  # Проверяем, есть ли ребро
                distance = current_distance + weight

                # Если найден новый кратчайший путь
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

def main():
    filename = input("Введите имя файла с весовой матрицей: ")
    weight_matrix = load_weight_matrix(filename)
    
    start_vertex = int(input("Введите номер начальной вершины: "))
    end_vertex = int(input("Введите номер конечной вершины: "))

    distances = dijkstra(weight_matrix, start_vertex)

    if distances[end_vertex] == float('inf'):
        print(f"Нет пути от вершины {start_vertex} до вершины {end_vertex}.")
    else:
        print(f"Оптимальный маршрут от вершины {start_vertex} до вершины {end_vertex} имеет вес: {distances[end_vertex]}")

if __name__ == "__main__":
    main()

Описание программы:

1. Загрузка матрицы весов: Программа загружает весовую матрицу из файла с помощью функции load_weight_matrix.
2. Алгоритм Дейкстры: Используется алгоритм Дейкстры для нахождения кратчайших расстояний от стартовой вершины ко всем остальным.
3. Ввод данных: Пользователь вводит имя файла и номера начальной и конечной вершин.
4. Вывод результата: Программа выводит вес кратчайшего пути или сообщение о том, что пути нет.

Убедитесь, что файл с весовой матрицей и корретные номера вершин, соответствующие индексам в матрице, введены правильно. Если у вас есть другие вопросы или нужен дополнительный функционал, не стесняйтесь обращаться!