Алгоритм Дейкстры: должен ли он работать, если есть 2 несвязанных графа?

Question

В настоящее время я реализовал алгоритм Дейкстры, но проблема возникает, когда я тестирую свой алгоритм на графике, подобном следующему:

и пытаюсь перейти от C к BИ я знаю, почему это не работает.Но мне интересно, сработает ли нормальная реализация, если есть такой график?комментарии.

Answer 1

IsVisited здесь немного вводит в заблуждение, так как вы можете на самом деле посещать узлы, которые вы не можете получить от исходного узла.Я бы переименовал его в isProcessed.Чтобы проверить, можете ли вы добраться от исходного узла к другому узлу, вам нужно проверить, является ли его расстояние int.maxVal.

. Чтобы избежать переполнения, не выполняйте итерации соседей, когда currentVertex.ShortestDistanceFromTarget равен int.maxVal, так какэто уже недоступный узел из исходного узла.