Поиск кратчайших путей взвешенного графика с использованием стеков

Question

Мне будет дан какой-то график, как на картинке ниже. Я искал некоторые алгоритмы, но это швы, как будто мне невозможно понять их. Фактически с использованием Floyd–Warshall algorithm это возможно, но, к сожалению, мне разрешено использовать только стеки (вместо матриц). Я также искал Dijkstra's algorithm, но я не мог получить отношения с моей проблемой.

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

Заранее спасибо.

Answer 1

Если вы просто хотите иметь значения всех кратчайших путей от выбранного узла до всех других узлов, вы будете в порядке с алгоритмом Дейкстры - это в основном расширенная BFS. Как только вы получите идею BFS, у вас не должно возникнуть проблем с пониманием Dijkstra. На самом деле намного проще реализовать BFS с одним queue, чем с arrays. Это какое-то формальное (школьное?) Требование, которое вы должны использовать stacks. Если так, то это довольно странно ... Но вы все еще можете эмулировать - совершенно неэффективным способом - queue с двумя stacks.

(кстати. DFS использует стек)

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

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

Если у вас есть Silverlight плагин, вы можете попробовать это небольшое приложение на 50%, написанную мной: http://grzesiaka.home.pl/GraphTutor/ вы найдете там презентацию шаг за шагом алгоритмов вы заинтересованы в (со структурами данных и псевдо-кода). Надеюсь, это поможет вам!