Алгоритм Флойда-Варшалла на ориентированном графе, в котором длина каждого ребра равна -1, 0 или 1

Question

Я беру курс Алгоритмы: проектирование и анализ II , и один из вопросов следующий:

Предположим, что мы запускаем алгоритм Флойда-Варшалла наориентированный граф G = (V,E), в котором длина каждого ребра равна -1, 0 или 1. Предположим также, что G сильно связан, по крайней мере, с одним u-v путем для каждой пары u,v вершин.График G может иметь или не иметь цикл отрицательной стоимости.Насколько большими могут быть конечные записи A[i,j,n] в абсолютном значении?Выберите наименьшее число, которое гарантированно будет действительной верхней границей.(Как обычно, n обозначает |V|.) [ВНИМАНИЕ: для этого вопроса обязательно обращайтесь к реализации алгоритма Флойда-Варшалла, приведенной в лекции, а не к какому-либо альтернативному источнику.]

• 2 ^ n
• n -1
• n ^ 2
• бесконечность

Ссылка на видео лекциина YouTube .Для справки, алгоритм выглядит следующим образом:

for k = 1 to n
  for i = 1 to n
    for j = 1 to n
      A[i,j,k] = min {A[i,j,k-1], A[i,k,k-1] + A[k,j,k-1]}

Правильный ответ - первый, 2^n, и подсказка говорит, что это может быть доказано по индукции.Я не могу обернуть голову вокруг этого.Может кто-нибудь помочь мне понять?

Answer 1

Рассмотрим график, на котором все узлы связаны со всеми остальными узлами с ребром длины -1.

Индукция может быть выполнена на k.Докажем следующее выражение:

A[i,j,k] = -2 ** k

Для k = 0, A[i,j,k] = -1 (по определению графика).Итак, базовое условие проверено.

Теперь A[i,j,k] = min(A[i,j,k-1], A[i,k,k-1] + A[k,j,k-1]).Используя индуктивную гипотезу, все слагаемые справа будут -2 ** (k - 1).

Следовательно, A[i,j,k] = -2 ** k и abs(A[i,j,n]) = 2 ** n.