Оптимальный путь в графе

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

https://contest.yandex.ru/test... 8209eacac2

В вашей программе обязательно должна присутствовать рекурсивная функция way(), которая и выполняет рассчет.
Формат ввода
В графе вершины пронумерованы. Граф является связанным, веса задаются методом, который называется «список ребер».

Входные данные имеют вид:

1 2 10
2 5 6
2 3 1
3 4 1
4 5 2
1 5


Расшифруем, что означает эта запись:
1. Вершины 1 и 2 связаны ребром с весом 10,
2. Вершины 2 и 5 – ребром с весом 6,
3. Вершины 2 и 3 – ребром с весом 1
и т.д.
Последняя строка говорит о том, из какой вершины в какую надо найти оптимальный путь. В нашем случае, из первой вершины в пятую.

Формат вывода
Наименьший по сумме весов путь для указанных вершин через запятую и пробел.

1, 2, 3, 4, 5
Примечания
Мы думаем, что вам будет интересно прочитать про различные алгоритмы поиска в графе, например про алгоритм Дейкстры, волновой алгоритм и алгоритм «поиска в ширину».

0

Не советую скатывать задание такой сложности )

0

getsugatenshoo, советую посмотреть на дату поста прежде чем что то писать

0

Semen-Semenich, Вопрос помечен решённым? И да, люди-то ищут и сейчас, задания не поменялись

0