1

Я неплохо разобрался в алгоритме флойда, но один вопрос ещё остался: почему вложенности циклов именно в таком порядке?

Почему алгоритм работает некорректно, если их поменять местами?

Например, при таком порядке перебора вершин алгоритм не работает:

Начальная вершина
Конечная вершина
Промежуточная вершина

А вот при таком порядке всё правильно:

Промежуточная вершина
Начальная вершина
Конечная вершина

В чём же разница? Как это работает? Объясните, пожалуйста.

0

1 ответ 1

4

Вся идея алгоритма Флойда заключается в том, что он одновременно решает задачу кратчайшего пути для всех пар вершин в графе, а не для одной конкретной пары i, j.

Если рассматривать схему реализации из Википедии

for k = 1 to n
  for i = 1 to n
    for j = 1 to n
      W[i][j] = min(W[i][j], W[i][k] + W[k][j])

то вся идея формирования матрицы W в алгоритме Флойда заключается в том, что новые значения матрицы W для шага k формируются на основе "старых" значений матрицы W (c шага k - 1). Как вы сами видите, при формировании элемента W[i][j] используются "старые" значения из посторонных элементов W[i][k] и W[k][j]. Они должны быть к этому моменту уже готовы, т.е. полная матрица W для значения k - 1 должна быть уже сформирована.

То есть для того, чтобы выполнять перевычисление W на шаге k нам надо иметь полностью сформированную W с шага k - 1. Вот поэтому цикл по k и сделан самым внешним.

Если вы просто ни о чем не задумываясь поменяете местами циклы

for i = 1 to n
  for j = 1 to n
    for k = 1 to n
      W[i][j] = min(W[i][j], W[i][k] + W[k][j])

то при выполнении внутреннего цикла по k будет происходить обращение к W[i][k] и W[k][j], которые не имеют никакого отношения к шагу k - 1 (они будут содержать либо начальные значения, либо финальные значения этого элемента) . Алгоритм не будет работать правильно.

Если вам захочется вдруг внешние циклы сделать по i и j, то фактически вы будете применять алгоритм Флойда к каждой паре i, j в отдельности. Получится что-то вроде

for i = 1 to n
  for j = 1 to n
  {
    /* Применяем алгоритм Флойда для пары `i, j` */

    /* Переинициализируем матрицу `W` */

    for k = 1 to n
      /* Формируем матрицу `W` шага `k` для пары `i` И `j` */
      for ii = 1 to n
        for jj = 1 to n
          W[ii][jj]= ...
  }

Теперь вам придется формировать полную матрицу шага k для пары i И j - а это снова циклы по ii и jj. Такая реализация будет весьма неразумной.

Так как матрица W шага k является актуальной для всех пар i, j одновременно, разумно обрабатывать шаг k именно так: для всех пар i, j одновременно.

1
  • Спасибо. Теперь, когда я взял информацию и у вас, и у преподавателя, я наконец понял что к чему. Это же элементарно, странно вообще, что понял не сразу :D
    – witaway
    21 мар 2017 в 17:32

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.