Floyd-Warshall avec des cycles négatifs. Comment trouver tous les chemins non définis?

Eh bien, j'ai trouvé une solution à mon propre problème.

for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)    // Go through all possible sources and targets

        for(int k = 0; d[i][j] != -INF && k < n; k++)
            if( d[i][k] != INF && // Is there any path from i to k?
                d[k][j] != INF && // Is there any path from k to j?
                d[k][k] < 0)      // Is k part of a negative loop?

                d[i][j] = -INF;   // If all the above are true
                                  // then the path from i to k is undefined

L'algorithme Floyd-Warshall affiche le résultat correct tant qu'aucun négatif Les cycles existent dans le graphique d'entrée. En cas d'existence d'un cycle négatif, calculer un chemin le plus court (simple) est un problème durs NP et le L'algorithme Floyd-Warshall n'étisera pas le résultat correct.

Mais il est possible de détecter la présence d'un cycle négatif en vérifiant qu'il existe une entrée négative dans la diagonale de la matrice. Ceci est fait dans la ligne 8 et la ligne 9 de cet algorithme: xxx

source

J'ai un vidéo qui explique exactement comment l'algorithme Floyd-Warshall fonctionne. Essentiellement, l'algorithme Floyd-Warshall est utilisé pour trouver les chemins les plus courts entre toutes les paires de nœuds dans un graphique pondéré avec des poids de bord positif ou négatif.

L'algorithme suivant accepte une matrice d'adjacence, où la double.Positive est utilisée pour indiquer que deux nœuds ne se connectent pas. Pour chaque nœud, vous voudrez également initialiser un poids de 0 à lui-même. P>

Cette méthode met à jour la matrice initiale pour indiquer la distance minimale entre toutes les paires de nœuds. Si le chemin le plus court est arbitrairement petit, la réponse est stockée en tant que double.Negative_infinity. Si deux nœuds ne peuvent pas se rejoindre, il est encore double. Positive_infinity. Cette mise en œuvre fonctionne deux fois et si la longueur du chemin est plus petite que celle-ci, nous sommes dans un cycle négatif. P>

static void floydWarshall(double[][] dist) {

  int n = dist.length;

  // Compute shortest paths
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (dist[i][k] + dist[k][j] < dist[i][j])
          dist[i][j] = dist[i][k] + dist[k][j];

  // Identify negative cycles
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (dist[i][k] + dist[k][j] < dist[i][j])
          dist[i][j] = Double.NEGATIVE_INFINITY;

}