Алгоритмы и структуры данных. Графы

Задача

Подсчет расстояний от произвольной вершины до всех остальных вершин в ориентированном ненагруженном графе. Реализовать алгоритм на языке С++ с использованием объектов и возможностей STL.

Выбрать оптимальную структуру данных для представления графа в памяти ЭВМ. Реализовать граф как объект, а обработку — как функцию-член для него. Результат обработки может быть или не быть частью объекта, способ его представления выбирается особо.

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

Стек и очередь (если нужны) берутся из STL.

Интерфейс программы должен быть удобен для испытаний алгоритма. Следует предусмотреть ввод заранее заготовленных и генерацию произвольных тестовых данных. 

Дополнительное требование: оценить возможный объем исходных данных для решения поставленной задачи для следующих ограничений:

— возможность вывода данных на экран;

— доступный объем памяти;

— получение решения за разумное время.

План записки

1. Текст индивидуального задания.

2. Математическая формулировка задачи в терминах теории множеств.

3. Выбор и обоснование способа представления данных.

4. Описание алгоритма и оценка его временной сложности.

5. Набор тестов и результаты проверки алгоритма на ЭВМ.

6. Выводы.

7. Список использованных источников.

8. Приложение: исходный текст программы для ЭВМ (на машинном носителе), файлы с тестами.

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