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

Question

Я применяя всю-пару кратчайшего пути алгоритм (Floyd-Warshall) этот ориентированного граф: alt text http://www.freeimagehosting.net/uploads/99b00085bf.jpg

На графике представлена ​​своей матрицей смежности. Простой код выглядит следующим образом:

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 до бесконечности (теоретически) должно работать.

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

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