Все пары алгоритма кратчайшего пути с одной матрицей - PullRequest
Новая
       3

Все пары алгоритма кратчайшего пути с одной матрицей

0 голосов
/ 13 декабря 2011

Я читаю об алгоритме Всех пар кратчайшего пути в структурах данных и анализе алгоритмов по книге Вессиса

Как показано в псевдо-коде ниже, когда k> 0, мы можем написать простую формулу для Dk, I, J.Кратчайший путь от vi до vj, который использует только v1, v2,.,,vk как промежуточные звенья - это кратчайший путь, который либо вообще не использует vk в качестве промежуточного звена, либо состоит из объединения двух путей vi vk и vk vj, каждый из которых использует только первые k - 1 вершины в качестве промежуточных звеньев.Это приводит к формуле

Dk, i, j = min {Dk - 1, i, j, Dk - 1, i, k + Dk - 1, k, j}

.требование времени снова O (| V | 3).Поскольку k-я стадия зависит только от (k - 1) -го этапа, оказывается, что только два | V |X | V |Матрицы должны быть сохранены.Однако использование k в качестве промежуточной вершины на пути, который начинается или заканчивается k, не улучшает результат, если не существует отрицательного цикла.Таким образом, необходима только одна матрица, потому что Dk-1, i, k = Dk, i, k и Dk-1, k, j = Dk, k, j, что подразумевает, что ни один из членов справа не меняет значения инеобходимо сохранить.

Мои вопросы:

  1. Что автор имеет в виду под "Однако, используя k в качестве промежуточной вершины на пути, который начинается или заканчиваетсяс k не улучшает результат, если нет отрицательного цикла "?

  2. Как автор пришел к выводу, что" Dk-1, i, k = Dk, i, k и Dk-1,k, j = Dk, k, j "?

Может кто-нибудь объяснить с простым примером 

/* Compute All-Shortest Paths */

/* A[] contains the adjacency matrix */

/* with A[i][i] presumed to be zero */

/* D[] contains the values of shortest path */

/* |V | is the number of vertices */

/* A negative cycle exists iff */

/* d[i][j] is set to a negative value at line 9 */

/* Actual Path can be computed via another procedure using path */

/* All arrays are indexed starting at 0 */



void

all_pairs( two_d_array A, two_d_array D, two_d_array path )

{

int i, j, k;



/*1*/        for( i = 0; i < |V |; i++ ) /* Initialize D and path */

/*2*/               for( j = 0; j < |V |; j++ )

{

/*3*/                  D[i][j] = A[i][j];

/*4*/                  path[i][j] = NOT_A_VERTEX;

}

/*5*/        for( k = 0; k < |v |; k++ )

/* Consider each vertex as an intermediate */

/*6*/        for( i = 0; i < |V |; i++ )

/*7*/                  for( j = 0; j < |V |; j++ )

/*8*/                       if( d[i][k] + d[k][j] < d[i][j] )

/*update min */

{

/*9*/                            d[i][j] = d[i][k] + d[k][j];

/*10*/                           path[i][j] = k;

}

}

1 Ответ

2 голосов
/ 13 декабря 2011

Вот ответы на ваши вопросы.

1) Алгоритм Флойд использует рекуррентное уравнение динамического программирования для определения кратчайших путей всех пар среди вершин;повторение основано на том факте, что для того, чтобы найти кратчайший путь между парой вершин i и j , необходимо проверить, идет ли он непосредственно от i до j дешевле, чем переход от i к промежуточной вершине k , а затем от k до j ,Вы проверяете это для всех вершин i , j и k , так что сложность составляет O ( n ^ 3).Теперь рассмотрим это: если все веса неотрицательны, то понятие кратчайшего пути хорошо определено.Вместо этого, если есть отрицательные циклы, это понятие не имеет смысла.Зачем?Потому что если вы найдете отрицательный цикл на пути от вершины i к вершине j , то вы можете проходить цикл столько раз, сколько пожелаете, и каждый раз, когда вы проходитецикл, стоимость соответствующего пути уменьшается, потому что веса на ребрах, принадлежащих циклу, являются отрицательными.Таким образом, отрицательный цикл, очевидно, улучшает стоимость кратчайшего пути (стоимость уменьшается).Поэтому важно иметь возможность обнаруживать отрицательные циклы, если вы разрешаете отрицательные веса на краях.Алгоритм Флойд предполагает, что ребра положительны, но способен обнаружить отрицательный цикл.

2) Уравнение повторения следующее, слегка упрощенное с учетом вашей записи: 

d[i, j] <- min(d[i, j], d[i, k] + d[k, j])

thisфактически используется, как показано в следующем псевдокоде 

for k <- 0 to n-1
   for i<- 0 to n-1
      for j <- 0 to n-1
         d[i, j] <- min(d[i, j], d[i, k] + d[k, j])

Каждое обновление d [i, j] требует доступа к d [i, k] и d [k, j], поэтому автор спрашивает:обновление d [i, j] требует значений d [i, k] и d [k, j], как мы можем быть уверены, что эти значения уже были вычислены во время k -й итерации?Как мы можем быть уверены, что эти значения не изменятся во время k -й итерации?

На самом деле эти значения не могут измениться во время k -й итерации, так чтонет функциональной зависимости.Вот почему.Действительно, во время итерации k обновление d [i, k] принимает форму 

d[i, k] <- min(d[i, k], d[i, k] + d[k, k])

, но d [k, k] равно нулю, так что d [i, k] не изменяется.

Аналогично, обновление для d [k, j] равно 

d[k, j] <- min(d[k, j], d[k, k] + d[k, j])

, так что d [k, j] тоже не меняется.

...