Реализация алгоритма Дейкстры

Question

Мне поручили (курсовая работа @ университет) внедрить форму поиска пути.Теперь, в спецификации, я мог бы просто реализовать грубую силу, поскольку существует ограничение на количество узлов для поиска (начало, два в середине, конец), но я хочу повторно использовать этот код и пришел к реализации Алгоритм Дейкстры .

Я видел псевдо в Википедии, и один мой друг тоже написал мне, но это не имеет смысла.Алгоритм кажется довольно простым, и для меня не проблема понять его, но я просто не могу представить себе код, который бы реализовал такую ​​вещь.

Есть предложения / советы?

Изменить для некоторых недоразумений:
Да, есть целевой узел и исходный узел.
Я рассчитываю реализовать Дейкстру в общем случае, а не в случае «только двух промежуточных остановок», потому что впоследствии я хочу снова использовать код.Иначе, я бы просто написал реализацию методом грубой силы.
Конкретная проблема, с которой у меня возникли небольшие проблемы, - это хранение неоптимальных полусформированных путей на случай, если они могут стать оптимальными.Когда я посещаю данный узел, я просто не вижу, как я собираюсь обновить все соединения, которые проходят через него.
Больше править:
Проходя через пару ответов сейчас и имеяgo.

ДЕЙСТВИТЕЛЬНО РЕДАКТИРОВАТЬ: Я забыл упомянуть серьезное осложнение, заключающееся в том, что любые две вершины могут иметь до UINT_MAX разного расстояния между ними.Сожалею.Фактически, тот факт, что я забыл разобраться с этим, вероятно, является причиной этой чертовой проблемы, хотя решение: выбрать самый короткий, к счастью, очевидно для меня.Неудивительно, что псевдо-переменные других людей для переменной расстояния не учитывали мою переменную расстояния.

Answer 1

Вот высокоуровневая разбивка алгоритма Дейкстры:

Вы помещаете все вершины в приоритетную очередь, где все вершины имеют приоритет (расстояние) бесконечности , кроме дляисходная вершина с нулевым расстоянием (исходная вершина равна нулю на расстоянии от себя, не так ли?).

Выдвиньте приоритетную очередь.Удаленная вершина является вершиной с кратчайшим расстоянием от источника.Очевидно, что первая вершина, выдвинутая из очереди, является источником.Хорошо, назовите эту вытянутую вершину v .

Посмотрите на каждого из соседей v .Все они будут иметь расстояние, превышающее расстояние v (в противном случае мы бы уже вытолкнули их из очереди, верно?).Допустим, v имеет расстояние 3, а v имеет 3 соседей x (dist-from-source: 5), y (dist-from-source: 10) и z (dist-from-source: infinity).

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

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

Answer 2

Внедрение алгоритма Дейкста в 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"
};

Это основано на первых нескольких строках псевдокода. Graph может быть std::vector<Vertex> вместе с некоторым способом определения расстояния между двумя вершинами.

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.

Answer 3

Первое, что вам нужно, это способ представления графика.Обычно это коллекция vertex объектов, каждый из которых содержит список смежности.В c ++ это может быть список указателей на другие вершины.Убедитесь, что вершины являются LessThanComparable.Вы можете, например, дать каждому уникальный идентификационный номер.

Тогда код в Википедии должен иметь больше смысла.Каждый раз, когда у вас есть псевдокод типа dist[v], вы хотите использовать map<VertexIdNumber, double>.

Answer 4

Ссылка на статью в Википедии , которую я вставил в ОП, дает очень четкое и краткое описание вместе с анимированной графикой.

Ключ, который может отсутствовать (?), Заключается в том, что на каждом шаге алгоритма вы, возможно, будете обновлять кратчайший путь для каждого узла, подключенного к вашему «текущему» узлу. В случае с четырьмя узлами «ромб», если A - начало, а D - конец, сначала вы вычисляете расстояния до B и C, затем из B вы вычисляете расстояние от A до D, затем вы делаете это также через C. путь через C короче, тогда «кратчайший путь от A до D» проходит через C. Если путь через C длиннее, то самый короткий путь проходит через B. Это, очевидно, должно (?) распространяться на более сложные сети.

На операторе Действительно редактировать : Неважно, сколько у вас соединений между двумя узлами. Действительно, в этом суть алгоритма, проверьте все соединения по всем возможным путям. Если узел A и узел B соединены двумя дорогами, и вы хотите самую короткую дорогу, не беспокойтесь о более длинной дороге, просто выбросьте ее. Всегда старайтесь отбросить данные, которые, как вы знаете, не имеют отношения к вашей проблеме.

Answer 5

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

Для начала нужно уточнить, является ли

1. ребра между узлами имеют разный вес
2. график направлен или ненаправлен

Прошло 25 лет с тех пор, как я изучал такие алгоритмы в университете, но по памяти алгоритм Варшалла легче реализовать матричным методом. Вы можете посмотреть здесь: www.ugrad.cs.ubc.ca / ~ cs490 / Spring05 / notes / graph_part3.pdf] .

Answer 6

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

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

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

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

Надеюсь, это поможет:)