Нахождение кратчайших путей взвешенного графа с использованием стеков
Мне дадут какой-то график, как на картинке ниже. Я искал некоторые алгоритмы, но кажется, что мне что-то невозможно понять. Фактически используя Алгоритм Флойда – Варшалла Это возможно, но, к сожалению, мне разрешено использовать только стеки (вместо матриц). Я тоже искал Алгоритм Дейкстры но я не мог получить отношения с моей проблемой.
Очевидно, моя цель — получить все кратчайшие пути из одной точки в другую. Как я уже говорил, я просто выведу решение из моего стек в векторной строке. Я предполагаю, что должен посетить каждый узел, и больше всего я боюсь зацикливаться на нем или даже терять дорожку во время поиска.
Также обратите внимание, что это не ориентированный граф. Если алгоритм Дейкстры здесь применим, я был бы очень признателен, если бы кто-нибудь из вас помог мне, и я был бы очень признателен за любую помощь, предложение, идею или даже видение, чтобы не зацикливаться или не терять дорожку во время поиска.
Заранее спасибо.
Решение
Если вы просто хотите получить значения всех кратчайших путей от некоторого выбранного узла ко всем остальным узлам, вам будет хорошо с алгоритмом Дейкстры — это в основном расширенная BFS. Как только вы поймете идею BFS, у вас не должно возникнуть проблем с пониманием Дейкстры. На самом деле гораздо проще реализовать BFS с одним queue чем с arrays,
Это какое-то формальное (школьное) требование, которое вы должны использовать stacks, Если это так, то это довольно странно … Но вы все еще можете подражать — совершенно неэффективно — queue с двумя stacks,
(кстати. DFS использует стек)
Если вы хотите иметь все все кратчайшие пути от всех узлов ко всем остальным узлам, вы можете просто запустить Dijkstra с каждого узла или попробовать Bellman-Ford, который немного быстрее, но немного сложнее понять.
Если вы хотите просто кратчайший путь от одного узла к другому, лучше всего использовать двунаправленную BFS (с расширенным битом).
Если у вас есть плагин Silverlight, вы можете попробовать это небольшое приложение на 50%, написанное мной:
http://grzesiaka.home.pl/GraphTutor/ Там вы найдете пошаговую презентацию интересующих вас алгоритмов (со структурами данных и псевдокодом). Надеюсь, это поможет вам!
Другие решения
Других решений пока нет …