Язык программирования 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 Теперь предположим, что между ними не будет никакого промежуточного значения. И это то, что я должен напечатать. Я действительно был бы признателен за любую помощь, предложение, которое вы можете мне дать


c algorithm shortest-path
person bledi    schedule 11.06.2012    source источник
comment
Используйте рекурсию для создания списка точек и распечатайте его, когда рекурсия вернется. В любом случае, это домашнее задание?   -  person kol    schedule 11.06.2012
comment
но как мне использовать рекурсию? НЕТ, это не домашнее задание   -  person bledi    schedule 11.06.2012
comment
Как вы храните свои очки? Если ваши точки поддаются хранению в структуре графа (большинство систем точек в основном попадают в структуру графа), один из лучших способов решить эту проблему - использовать алгоритмы построения графиков.   -  person NKamrath    schedule 11.06.2012
comment
Какой алгоритм вы используете? Дийкстра?   -  person kol    schedule 11.06.2012
comment
Вы представляете (или можете ли вы) точки в своей программе как узлы в структуре данных Graph? Используя график, вы можете реализовать алгоритм Floyd-Warshall и получить минимальное расстояние между всеми узлами графика   -  person higuaro    schedule 11.06.2012
comment
Я использовал алгоритм Флойда-Уоршалла, но мне не нужно одно расстояние. Я имею в виду, что хочу найти весь путь   -  person bledi    schedule 11.06.2012
comment
Да, алгоритм Дейкстры является наиболее эффективным алгоритмом SSSP (кратчайший путь из одного источника). en.wikipedia.org/wiki/Dijkstra's_algorithm. Floyd-Warshall будет работать нормально, за исключением того, что он медленнее, чем у Дейкстры. Dijkstra O (e + vlgv), где as floyd-warshall - o (v ^ 3). Дийкстра намного лучше   -  person NKamrath    schedule 11.06.2012

Ответы (2)


arrow_upward
2
arrow_downward

Алгоритм Варшалла-Флойда (используемый OP) имеет версию, которая может определять путь в дополнение к расстоянию между узлами графа:

алгоритм Флойда-Уоршалла с реконструкцией пути

Однако следует отметить, что это не лучший алгоритм для решения проблемы кратчайшего пути. .

person kol    schedule 11.06.2012
comment
Дейкстра намного быстрее. Он также имеет реконструкцию пути и, на мой взгляд, намного проще, потому что реконструкция пути встроена в функциональность. Флойд-Уоршалл очень медленный, особенно для больших графов. Проверьте вики en.wikipedia.org/wiki/Dijkstra%27s_algorithm - person NKamrath; 11.06.2012
comment
Что ж, насколько мне известно, O (V ^ 3) - ужасное время выполнения. O (E + V lg V) намного лучше. Флойд Уоршалл - ужасная рекомендация, особенно когда требуется реконструкция пути. - person NKamrath; 11.06.2012
comment
да, вы правы, но мне кажется, это намного сложнее реализовать - person bledi; 11.06.2012
comment
@NKamrath Вы абсолютно правы. Но OP использует FW, и ему нужна была только техника, чтобы найти путь в дополнение к расстоянию. В любом случае, спасибо за -1. Мир :) - person kol; 11.06.2012
comment
Если бы вы знали, о чем говорите, я бы не стал отказываться от вас. Поскольку вы ошибаетесь, я вынужден. SSSP - это то, о чем просили, а не ASSP, который вы предоставили, который дает человеку, которому вы помогли, алгоритм, который будет работать намного дольше, чтобы вычислить то же самое, а затем потребовать от него дополнительных усилий для восстановления пути вместо повторения набора указателей в узлах графа. Надеюсь, ты никого не обманешь. - person NKamrath; 11.06.2012
comment
@NKamrath Хорошо, я изменил свой ответ. - person kol; 11.06.2012
comment
Спасибо, извините, я почти уверен, что я навязчиво привязан к алгоритмам. Я виню своих профессоров, что они разрушили мою жизнь, ха-ха. -1 удалено +1 добавлено - person NKamrath; 12.06.2012

arrow_upward
1
arrow_downward

Похоже, рекурсия - лучший способ сделать это. Если он уже может найти кратчайший путь, я предполагаю, что у вас есть функция, написанная для поиска кратчайшего пути между двумя точками. Возможно, вы могли бы рекурсивно разбить список, найти кратчайший путь и добавить эту точку в список.

Отредактируйте, извините, я неправильно понял ваш вопрос, вам нужно найти середину. Передайте рекурсивной функции весь список точек и найдите середину. Если он существует, добавьте его в список. Если нет средней точки, ничего не добавляйте. Продолжайте вызывать эту функцию до тех пор, пока не дойдете до базового варианта, который должен занимать 1 или 2 пункта в списке.

person element11    schedule 11.06.2012
comment
да, возможно, вы правы, если я использую массив для хранения элементов, как мне приступить к его обновлению? - person bledi; 11.06.2012
comment
Я бы подумал, что вы можете найти среднюю точку в позиции n / 2. Затем разделите список на 2 части от 1 до n / 2 и от n / 2 до n. Если в списке четное количество элементов, разбейте его на 2 списка от 1 до n / 2 - 1 и от n / 2 + 1 до n и не добавляйте среднюю точку к списку. Затем вызовите рекурсивную функцию в обоих списках. Чтобы обновить, вам нужно поставить середину в правильном месте. Это можно сделать, отслеживая, где вы находитесь в списке. Дай мне подумать об этом на секунду - person element11; 11.06.2012
comment
Я думаю, что это немного сложно, потому что, если я найду среднюю точку, список должен быть сдвинут. Во-вторых, как будет работать следующая итерация, я имею в виду, будет ли она принимать старые значения или обновленные? Я думаю, что могут быть значения, которые будут проигнорированы на следующей итерации - person bledi; 11.06.2012
comment
Элемент имеет право делить n / 2, взять результат и составить два списка. n = количество элементов в списке. subList1 = элементы от 0 до n; sublist2 = элементы от n + 1 до n. Затем рекурсивно разбейте эти списки, используя ту же функцию. Когда в списке осталось менее 2 или менее элементов, начните добавлять их в список промежуточных точек. вы должны убедиться, что вы вызываете рекурсию в первой части, а затем во второй, чтобы получить правильно упорядоченное решение. Список решений должен быть возвращен и добавлен к каждому уровню до завершения рекурсии. - person NKamrath; 11.06.2012