Что мне недостает в моем алгоритме Warshall?

Я пытаюсь реализовать алгоритм Варшалла, чтобы найти транзитивное замыкание матрицы смежности. Это то, что у меня есть для функции:Что мне недостает в моем алгоритме Warshall?

public static int[][] warshall(int A[][]){ 
    int R[][] = A; 
    for (int k = 1; k < n; k++) { 
     for (int i = 1; i < n; i++) { 
      for (int j = 1; j < n; j++) { 
       if ((R[i][j] == 1) || ((R[i][k] == 1) && (R[k][j] == 1))) { 
        A[i][j] = 1; 
       } 
      } 
     } 
     R = A.clone(); 
    } 
    return A; 
}

Я использую следующую матрицу смежности для теста:

Который должен привести:

Я не приближаясь к этому. Может ли кто-нибудь с легкостью увидеть то, что мне не хватает?

Спасибо за любые советы или предложения.

источник

2014-11-02 Captain n00b

Я не вижу какой-либо часть этого кода пересекает вершины или ребра. Кроме того, что такое 'n'? Он не определен нигде в этом блоке кода. – Makoto

Граф также может быть представлен как матрица –

Я не знаком с этим конкретным алгоритмом, но в Java и многих других языках (большинство из них на самом деле), вы всегда должны начать ваше для петель с индексом 0 и НЕ 1.

источник

2014-11-02 05:55:22 Eric

Это может быть транслитерация [Floyd-Warshall] (http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm), в которой циклы начинаются при 1 и продолжаем | V |. – Makoto

Вау ... Не могу поверить, что я даже потрудился с этим вопросом. Книга, которую я использую в качестве ссылки, содержит алгоритм, в котором инициализируется каждый итератор 1, и вместо того, чтобы просто проверять это, я просто предположил, что это правильно. Приношу свои извинения за неосведомленный вопрос, и спасибо за отзыв о чем-то, что я должен был попробовать с самого начала. –

haha, np. Отметьте его как принятое тогда =) – Eric

Что мне недостает в моем алгоритме Warshall?

ответ

Смежные вопросы