Оптимальный путь

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



В вашей программе обязательно должна присутствовать рекурсивная функция 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