Язык программирования C, кратчайший путь
Я пишу код, чтобы найти кратчайшее расстояние между двумя точками. Мой код работает отлично до сих пор. Я имею в виду, что он находит расстояние и путь, по которому они должны пройти. Мне нужно распечатать эту информацию, но я должен сделать функцию печати. Это работает примерно так: например, начальная точка - 4, а последняя - 13.
Я должен придумать алгоритм, который проверяет их промежуточные точки. Скажем, между 4 и 13 есть точка: 7
4--7--13 Теперь мне нужно проверить каждую точку между ними, как:
4--6--7--9--13 Чтобы быть более точным, он проверит, есть ли точка между 4-6 и 6-7 и 7-9 и 9-13. Поэтому в следующей итерации может быть сформирован еще один список:
4--2--6--7--5--9--17--13 Теперь предположим, что между ними не будет промежуточных значений. И это то, что я должен напечатать. Я действительно буду признателен за любую помощь, предложение, которое вы можете дать мне
2 ответа
Алгоритм Варшалла-Флойда (используемый ОП) имеет версию, которая может определять путь в дополнение к расстоянию между узлами графа:
Алгоритм Флойда-Варшалла с реконструкцией пути
Однако следует отметить, что это не самый лучший алгоритм для решения проблемы кратчайшего пути.
Похоже, рекурсия была бы лучшим способом сделать это. Если он уже может найти кратчайший путь, я предполагаю, что у вас есть функция, написанная для поиска кратчайшего пути между 2 точками. Возможно, вы могли бы рекурсивно разбить список, найти кратчайший путь и добавить эту точку к списку.
Изменить, извините, я неправильно прочитал ваш вопрос, вам нужно найти середину. Передайте рекурсивной функции весь список точек и найдите середину. Если он существует, добавьте его в список. Если середины нет, ничего не добавляйте. Продолжайте вызывать эту функцию, пока не дойдете до базового варианта, который должен составлять 1 или 2 пункта в списке.