Алгоритм Дейкстры - алгоритм жадного или динамического программирования?

Ответ 1

Это жадный, потому что вы всегда отмечаете ближайшую вершину. Он динамический, поскольку расстояния обновляются с использованием ранее вычисленных значений.

Ответ 2

Я бы сказал, что это определенно ближе к динамическому программированию, чем к жадному алгоритму. Чтобы найти кратчайшее расстояние от A до B, он не решает, какой путь идти шаг за шагом. Вместо этого он находит все места, из которых можно перейти от A, и отмечает расстояние до ближайшего места. Однако указание на это место не означает, что вы пойдете туда. Это означает, что расстояние больше не может быть сокращено, если все ребра графа положительны. Сам алгоритм не имеет хорошего направления в отношении того, каким образом вы быстрее разместите B. Оптимальные решения не принимаются жадно, но сделаны путем исчерпания всех возможных путей, которые могут сделать расстояние короче. Следовательно, это алгоритм динамического программирования, единственное изменение заключается в том, что этапы не известны заранее, но динамически определяются в ходе алгоритма. Вы можете назвать это "динамическим" алгоритмом динамического программирования, если хотите, рассказать об этом отдельно от других алгоритмов динамического программирования с заранее определенными этапами принятия решений.

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