Алгоритм Дейкстры с 2d-массивом

Question

Последние несколько дней я пытался реализовать этот алгоритм.До сих пор мне удалось создать динамический 2d массив и вставить расстояния между узлами, функцию для удаления пути между узлами и функцию, которая сообщает мне, существует ли путь между двумя узлами.Теперь я хотел бы реализовать функцию, которая возвращает кратчайший путь от узла A к узлу B. Я знаю, как работает алгоритм dijkstras, и я прочитал псевдокод в вики, не имея возможности написать какой-либо код сам.Я действительно застрял здесь.

Я думал о том, как должен выглядеть код и что должно произойти, поэтому я создал функцию, которая сообщает мне, есть ли путь между двумя узлами.Нужны ли мне еще какие-нибудь вспомогательные функции, которые облегчили бы реализацию dijkstras?

Пока у меня есть только 3 узла, но код, который я хотел бы написать, должен работать в целом для n узлов.* Любая помощь приветствуется.

Answer 1

Вы, наверное, много думаете.

Вам нужно 2 вещи. Чистая графическая структура, которую вы понимаете. Хорошее описание алгоритма вы понимаете. Если у вас есть оба. Просто начните писать код. Необходимые помощники станут очевидными в пути.

- редактировать -
Вам, вероятно, понадобятся некоторые из следующих структур данных
std::vector std::list std::priority_queue

Answer 2

Редактировать : Код удален, и я собираюсь дать подсказки:

1. Сохранить график как список списков смежности каждой вершины.(что-то вроде этого vector < vector < pair<int,int> > > g (n);)
2. Используйте некоторую структуру данных, чтобы отслеживать, что такое вершина с минимальным расстоянием в текущем состоянии.(может быть установлено, или priority_queue, чтобы иметь O(m log(n)) сложность)
3. Каждый раз принимать вершину high_priority (вершину с минимальным текущим расстоянием), удалять ее из вашей структуры данных и обновлять расстояния смежных с удаленными вершинами.

---

Примечание: Если вы также хотите получить минимальный путь, оставьте некоторое значение vector<int> previous и каждый раз при обновлении расстояния вершины (скажем, v) устанавливайте previous[v] = index of vertex from where you came here.Ваш путь last, prev[last], prev[prev[last]],...,first в обратном порядке.

Answer 3

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

Посмотрите на это и посмотрите, поможет ли это.

http://vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in-c-2/

Удачи.