Реализация алгоритма Dijkstra
Для меня определили задачу (курсовая работа университет) для реализации формы новаторских. Теперь, в спецификации, я мог просто реализовать грубую силу, так как существует предел на количество узлов для поиска (начните, два в середине, конце), но я хочу снова использовать этот код и приехал для реализации алгоритма Dijkstra.
Я видел псевдо на Википедию, и друг записал некоторым для меня также, но она утончается, не имеет смысла. Алгоритм кажется довольно простым, и это не проблема для меня для понимания этого, но я просто не могу ни за что в жизни визуализировать код, который понял бы такую вещь.
Какие-либо предложения/подсказки?
Редактирование для некоторых беспорядков:
Да, существует целевой узел и исходный узел.
Я надеюсь реализовывать Dijkstra в общем случае, не "только две промежуточных остановки" случай, потому что я хочу использовать код снова впоследствии. Еще, я просто записал бы реализацию "в лоб".
Конкретный вопрос, из-за которого я испытываю немного затруднений, хранит субоптимальные полусформированные пути, в случае, если они могут стать оптимальными. Когда я посещаю данный узел, я просто не вижу, как я собираюсь обновить все соединения, которые проходят его.
Больше редактирования:
Прохождение через нескольких ответов теперь и попытка.
ДЕЙСТВИТЕЛЬНО РЕДАКТИРОВАНИЕ: Я забыл упоминать серьезную сложность, которая является, что любые две вершины могут иметь до различных расстояний UINT_MAX между ними.Прошу прощения. Infact, то, что я забыл иметь дело с этим, является, вероятно, причиной проклятой проблемы во-первых, хотя решение: выбор самое короткое, к счастью, очевиден для меня. Неудивительные другие люди, псевдо для переменной расстояния, не приняли во внимание мое переменное расстояние.
6 ответов
Вот подробное описание алгоритма Дейкстры:
Вы вставляете все вершины в очередь с приоритетом, в которой все вершины имеют приоритет (расстояние) бесконечности , кроме для исходной вершины, которая имеет нулевое расстояние (исходная вершина находится на нулевом расстоянии от себя, верно?).
Удалить приоритетную очередь. Удаляемая вершина - это вершина, находящаяся на кратчайшем расстоянии от источника. Очевидно, что первая вершина, извлеченная из очереди, является источником. Назовем эту всплывающую вершину v .
Посмотрите на каждого из соседей v . Все они будут иметь расстояние больше, чем расстояние v (иначе мы бы уже вытащили их из очереди, верно?). Допустим, v имеет расстояние 3, а v имеет 3 соседей x (dist-from-source: 5), y (dist-from-source: 10) и z (dist-from-source: бесконечность).
Теперь посмотрим на расстояние каждого соседа от v .Допустим, они следующие: x - 3, y - 2, z - 4. Это означает, что путь от источника до x , который проходит через v , имеет расстояние | v | + 3 (3 + 3 = 6), y имеет расстояние 5 (3 + 2 = 5), а z имеет расстояние 7 (3 + 4 = 7).
Путь к x через v длиннее, чем текущий кратчайший путь к x , поэтому мы игнорируем его. Однако пути к y и z , которые проходят через v , короче, чем предыдущий известный кратчайший путь, поэтому мы обновляем их.
Продолжайте делать это, пока не пройдете все вершины. В каждой точке, когда вы извлекаете min из очереди приоритетов, вы знаете, что нашли кратчайший путь к этой вершине, потому что любой возможный более короткий путь должен проходить через вершину с расстоянием, меньшим, чем v , что означает, что мы уже вытащили это из очереди.
Реализация алгоритма Дейкста на C ++, если вы никогда не писали ничего подобного, является довольно сложной задачей. Прочитав страницу Википедии, вот несколько идей, с которых можно начать.
struct Vertex {
int id;
std::vector<int> neighbors;
int dist_from_source; // need some sentry value for "infinity"
int prev; // need some sentry value for "undefined"
};
Это основано на первых нескольких строках псевдокода. График может быть std :: vector вместе с некоторым способом определения расстояния между двумя вершинами.
8 u := vertex in Q with smallest dist[]
Эта строка указывает на необходимость в std :: make_heap (а не в priority_queue, как мы увидим позже). Создайте для этого отдельный вектор, потому что нам нужно будет добавлять и удалять элементы из него. Посмотрите, как предоставить предикат, который помещает вершину с наименьшим dist_from_source на вершину кучи.
12 for each neighbor v of u: // where v has not yet been removed from Q.
Вот почему мы не используем priority_queue для Q . Вам необходимо выяснить, находится ли v в Q . Priority_queue не позволяет вам этого делать.
13 alt := dist[u] + dist_between(u, v)
Теперь вам нужна функция расстояния, которая поставляется с Graph . Вы не сказали, как определяются данные графика, так что вы здесь как бы сами по себе.
17 return dist[]
Эта строка просто означает возврат любых данных, необходимых для создания кратчайших путей. По сути, это набор вершин со всеми заполненными prev и dist_from_source .
Первое, что вам нужно, это способ представления графика. Обычно это набор из объектов вершин , каждый из которых содержит список смежности. В C ++ это может быть список указателей на другие вершины. Убедитесь, что вершины LessThanComparable. Например, вы можете дать каждому уникальный идентификационный номер.
Тогда код в Википедии должен иметь больше смысла.Каждый раз, когда у вас есть псевдокод вроде dist [v] , вы хотите использовать карту .
Ссылка на статью Википедии , которую я вставил в OP, дает очень четкое и краткое описание вместе с анимированной графикой.
Ключ, который может отсутствовать (?), Заключается в том, что на каждом шаге алгоритма вы, возможно, будете обновлять кратчайший путь к каждому узлу, связанному с вашим «текущим» узлом. В случае «ромба» с четырьмя узлами, если A - начало, а D - конец, сначала вы вычисляете расстояния до B и C, затем от B вы вычисляете расстояние от A до D, затем вы делаете это также через C. путь через C короче, тогда «кратчайший путь от A к D» проходит через C. Если путь через C длиннее, то кратчайший путь проходит через B. Очевидно (?) он должен распространяться на более сложные сети.
В OP Really Edit : Неважно, сколько соединений у вас установлено между двумя узлами. Действительно, в этом суть алгоритма - проверить все соединения по всем возможным путям. Если узел A и узел B соединены двумя дорогами, и вам нужна самая короткая дорога, не беспокойтесь о более длинной дороге, просто выбросьте ее. Всегда старайтесь отбрасывать данные, которые, как вы знаете, не имеют отношения к вашей проблеме.
Конкретный вопрос, с которым я испытываю небольшие проблемы, - это хранение неоптимальных полусформированных путей на случай, если они могут стать оптимальными. Когда я посещаю данный узел, я просто не понимаю, как мне обновить все соединения, которые проходят через него.
Я думаю, возможно, вы немного неправильно понимаете алгоритм. Дейкстра работает, исследуя узлы в порядке возрастания расстояния; таким образом, вы гарантированно найдете минимальное расстояние и оптимальный путь к любому узлу, который был постоянно помечен.
Обычно при выполнении алгоритма вы не храните пути в явном виде. Вместо этого представьте, что вы строите на графе охватывающее дерево - так что есть только один способ добраться до каждого узла этого дерева. Все, что вам нужно хранить для каждого узла, - это метка расстояния и его родитель. Когда вы впервые видите каждый узел во время поиска, вы помечаете его предварительно; возможно, позже вы найдете лучший маршрут к нему - но все, что вам нужно обновить в этот момент, это метки расстояния и родителя для этого единственного узла.
Как только вы окончательно обозначите пункт назначения, вы можете остановиться, и тогда вы сможете получить оптимальный маршрут к нему, пройдя по родительским меткам обратно к источнику.
Надеюсь, это поможет :)
Этот ответ может быть слишком запоздалым для вас, но я предлагаю его на случай, если он поможет другим.
Во-первых, вам нужно выяснить, имеют ли
- ребра между узлами разный вес
- граф является направленным или неориентированным
Прошло 25 лет с тех пор, как я изучал такие алгоритмы в университете, но по памяти алгоритм Уоршалла таков. проще реализовать матричным методом. Вы можете посмотреть здесь: www.ugrad.cs.ubc.ca/~cs490/Spring05/notes/graph_part3.pdf] .