Сравнение алгоритмов Расст-Рек и Дейкстры

Сложность рекурсивного алгоритма пропорциональна N!, а алгоритм Дейкстры имеет сложность ~N2. Комментарии, как говорится, излишни.

  1)

  См. лекцию 11.

  2)

  См. лекцию 9.

  3)

  Точнее, результатом печати значений, содержащихся в вершинах ДСА.

  4)

  Вместо простой пометки вершины здесь можно производить выполнение любой осмысленной функции.

  5)

  См. лекцию 9.

  6)

  См. предыдущую лекцию.

  7)

  Dijkstra E.W. A Note on Two Problems in Connection with Graphs, 1959.

© 2003-2007 INTUIT.ru. Все права защищены.