Модификация алгоритма кратчайшего пути (маршрут от узла к себе)

Question

Я применяю алгоритм кратчайшего пути всех пар ( Флойд-Варшалл ) к этому ориентированному графу:

График представлен матрицей смежности. Простой код выглядит так:

public class ShortestPath {

public static void main(String[] args) {
    int x = Integer.MAX_VALUE;
    int [][] adj= {      
      {0, 6, x, 6, 7}, 
            {x, 0, 5, x, x}, 
            {x, x, 0, 9, 3}, 
            {x, x, 9, 0, 7}, 
            {x, 4, x, x, 0}};

    int [][] D = adj;

    for (int k=0; k<5; k++){
        for (int i=0; i<5; i++){
            for (int j=0; j<5; j++){
                if(D[i][k] != x && D[k][j] != x && D[i][k]+D[k][j] < D[i][j]){
                       D[i][j] = D[i][k]+D[k][j];                    
                   }
            }
        }       
    }

    //Print out the paths
    for (int r=0; r<5; r++) {
         for (int c=0; c<5; c++) {
             if(D[r][c] == x){
                 System.out.print("n/a"); 
             }else{
             System.out.print(" " + D[r][c]);
             }
         }
         System.out.println(" ");
     }
}

}

Вышеприведенное работает нормально, если речь идет об алгоритме.

Я пытаюсь указать, что путь от любого узла к самому себе является , а не обязательно 0, как подразумевается здесь при использовании матрицы смежности, но может быть любым возможным путем через другие узлы: Например B -...-...-...-B

Есть ли способ изменить мое текущее представление, чтобы указать, что кратчайший путь, скажем, от B до B, не равен нулю, а 12, следуя маршруту B-C-E-B? Можно ли это сделать, изменив метод матрицы смежности?

Answer 1

Изменение матрицы смежности диагональных элементов от 0 до бесконечности (теоретически) должно работать.

Это означает, что стоимость цикла самоконтроля бесконечна, и любой другой путь с меньшим, чем эта стоимость, лучше, следовательно, если путь существует от узла к себе, через другие узлы, его стоимость будет конечной, и она заменит бесконечное значение.

Практически вы можете использовать максимальное значение целого числа как бесконечное.