Реферат: Динамическое программирование, алгоритмы на графах
for i:=1 to n do
if (not b[i])and(l[i]<l[min]) then min:=i;
if l[min]< ¥ then
begin
p:=min; b[p]:=true; f:=true
end
end;
Несложно подсчитать, что трудоемкость алгоритма составляет O (N 2 ), что окупает некоторые сложности в его реализации. Как и в случае применения “волнового” алгоритма в невзвешенном графе, асимптотическая оценка не изменится если нам потребуется подсчитать длину пути от s до каждой из вершин графа. Поэтому, как и в алгоритме Флойда, длины кратчайших путей между всеми парами вершин могут быть рассчитаны за O (N 3 ) операций.
Заключение
Итак, неформально, граф можно определить как набор вершин (города, перекрестки, компьютеры, буквы, цифры кости домино, микросхемы, люди) и связей между ними: дороги между городами; улицы между перекрестками; проводные линии связи между компьютерами; слова, начинающиеся на одну букву и закачивающиеся на другую или эту же букву; проводники, соединяющие микросхемы; родственные отношения, например, Алексей - сын Петра. Двунаправленные связи, например, дороги с двусторонним движением, принято называть ребрами графа; а однонаправленные связи, например, дороги с односторонним движением, принято называть дугами графа. Граф, в котором вершины соединяются ребрами, принято называть неориентированным графом, а граф, в котором хотя бы некоторые вершины соединяются дугами, принято называть ориентированным графом.
Литература
1. Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М.: Лаборатория базовых знаний, 2000.
2. Станкевич А .С. Решение задач I Всероссийской командной олимпиады по программированию. “Информатика”, №12, 2001.
3. Окулов С.М. 100 задач по информатике. Киров: изд-во ВГПУ, 2000.
4. Андреева Е.В. Решение задач XIII Всероссийской олимпиады по информатике. “Информатика”, №19, 2001.
5. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: “Вильямс”, 2000.
6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.
7. Липский В. Комбинаторика для программистов. М.: “Мир”, 1988.
8. Вирт Н. Алгоритмы и структуры данных. Санкт-Петербург: “Невский диалект”, 2001.