| 1 ~SupernaturaL_kz~, 22 апреля 2011 г. 7:44:04 | |
Динамически находит кратчайшие пути между всеми парами вершин.
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
a[i,j]:=min(a[i,j],a[i,k]+a[k,j]);
Если что я его в тупую выучил, там больше ничего и не надо.
Я бы посоветовал понять, почему он работает. Это ни что иное, как динамическое программирование. Когда знаешь и понимашь почему это правильно, никогда не забудешь и сможешь вывести сам. Самая типичная ошибка на эту тему, это использование цикла по k внутри, что приводит к тому, что найденные пути могут быть не оптимальными.
|
|
|
