Блок задач

4. Один класс

Темы
Сложность 5

Задача «Алгоритм Дейкстры»

Реализовать алгоритм Дейкстры.

Входные данные

Текстовый файл содержащий номер вершины истока (S) и описание всех ребер графа в формате:

<вершина N>-<вершина K>-<вес ребра>

Типы данных:

string - string - unsigned int

Пример:

S Moscow
Moscow Novosibirsk 7
Moscow Toronto 9
Moscow Krasnoyarsk 14
Novosibirsk Toronto 10
Novosibirsk Omsk 15
Omsk Toronto  11
Toronto Krasnoyarsk 2
Krasnoyarsk Kiev 9
Kiev Omsk  6

Можно использовать любые разделительные знаки

Постановка задачи

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

Выходные данные

Текстовый файл с результатом работы алгоритма в формате:

Вершина - {кратчайший путь до нее} - общий вес пути

Пример (для вышеописанных входных данных)

Novosibirsk - {Moscow, Novosibirsk} - 7
Toronto - {Moscow, Toronto} - 9
Krasnoyarsk - {Moscow, Toronto, Krasnoyarsk} - 11
Omsk - {Moscow, Toronto, Omsk} - 20
Kiev - {Moscow, Toronto, Krasnoyarsk, Kiev} - 20