§ 44. Графы
- Напишите программу, которая вводит из файла весовую матрицу
графа и строит для него минимальное остовное дерево. - Оцените асимптотическую сложность алгоритма Прима-Крускала.
- Напишите программу, которая вводит из файла весовую матрицу
графа, затем вводит с клавиатуры номера начальной и конечной вер
шин и определяет кратчайший маршрут. - Напишите программу, которая вводит из файла весовую матрицу
графа и определяет длины всех кратчайших маршрутов с помощью
алгоритма Флойда-Уоршелла. - Оцените асимптотическую сложность алгоритмов Дейкстры и Флой
да-Уоршелла. - Напишите программу, которая решает задачу коммивояжёра для 5
городов методом полного перебора. Можно ли использовать её для 50
городов?
*7. Напишите программу, которая решает задачу 5 (о размещении школы). Для определения кратчайших путей используйте алгоритм Флойда-Уоршелла. Весовую матрицу графа вводите из файла.