Мне недавно пришлось взглянуть на алгоритм Дейкстры, и это доказательство.
Доказательство алгоритма заканчивается во всех источниках, которые я смог найти с равенством количества всех вершин и количества всех посещенных вершин (например, R = V или S = V).Более того, цикл while этого алгоритма завершается, когда Q (инициируемый как все вершины графа) становится пустым, поэтому необходимо посетить все вершины.
Я не понимаю, почему это так.Не существует графиков, где алгоритм не должен посещать все вершины, например: Начальная вершина связана с вершиной «найти» непосредственно с весом 1 и с другими вершинами с весом 10.
Надеюсь, выполучите проблему, которая у меня здесь.
Редактировать: Это псевдокод, который я использовал из Cormen:
