Курсовая работа: Кратчайшие пути

Задание

Имеется n городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей порядка n, элемент a_ij которой равен некоторому отрицательному числу, если город i не соединен напрямую дорогой с городом j, и равен длине дороги в противном случае (i,j = 1,...,n).

Написать программу, которая:

а) для первого города находит кратчайшие маршруты в остальные города;

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

Разрабатываемая программа должна:

а) выполнять сервисные функции:

- очистка используемой структуры данных (массива, массива записей, списка и т.п.);

- ввод значений (заполнение в оперативной памяти) используемой структуры данных;

- сохранение используемой структуры данных в файл; чтение используемой структуры данных из файла;

-вывод используемой структуры данных на экран; вывод решения на экран или в файл;

- добавление элементов в используемую структуру данных;

- удаление элементов из используемой структуры данных и др.

б) позволять запуск на выполнение с использованием параметров (ключей запуска), передаваемых через командную строку (в соответствии с вариантом задания); для каждого варианта задания необходимо определить и согласовать с преподавателем список и значения ключей запуска.

Все действия в программе (очистка, заполнение, запись элемента и т.д.) должны быть оформлены в виде подпрограмм.

Каждая подпрограмма должна размещаться в отдельном модуле.

Вызов подпрограмм выполнять только через указатели (на тип подпрограммы).

Для выполнения действий в программе должна быть предусмотрена и разработана система меню (не обязательно графического).

Результаты выполнения каждого действия должны выводиться на отдельном экране. Должна быть предусмотрена возможность вывода результатов в файл.