Trouver le cycle de la longueur la plus courte dans un graphe orienté avec des poids positifs

J'ai été demandé à cette question dans une interview, mais je ne pouvais pas venir avec toute solution décente. Donc, je leur ai dit que l'approche naïve de trouver tous les cycles en choissant le cycle avec le moins de longueur.

Je suis curieux de savoir ce qu'est une solution efficace à ce problème.

source d'informationauteur Chander Shivdasani

  1. 20

    Vous pouvez facilement modifier De Floyd-Warshall algorithme. (Si vous n'êtes pas familier avec la théorie des graphes à tous, je propose de le vérifier, par exemple, obtenir une copie de Introduction aux Algorithmes).

    Traditionnellement, vous commencez à path[i][i] = 0 pour chaque i. Mais à la place, vous pouvez commencer à partir de path[i][i] = INFINITY. Elle n'affectera pas l'algorithme lui-même, comme ces zéros n'ont pas été utilisées dans le calcul de toute façon (depuis le chemin path[i][j] ne changera jamais pour k == i ou k == j).

    En fin de compte, path[i][i] est la longueur du cycle le plus court en passant par i. Par conséquent, vous avez besoin de trouver min(path[i][i]) pour tous i. Et si vous voulez du cycle lui-même (et pas seulement de sa longueur), vous pouvez le faire, tout comme il est habituellement fait avec la normale des chemins d'accès: par la mémorisation de k lors de l'exécution de l'algorithme.

    En outre, vous pouvez également utiliser L'algorithme de Dijkstra de trouver un cycle le plus court en passant par un nœud donné. Si vous exécutez cette Dijkstra modifié pour chaque nœud, vous obtiendrez le même résultat qu'avec de Floyd-Warshall. Et depuis chaque Dijkstra est O(n^2)vous aurez le même O(n^3) complexité globale.

  2. 5

    Le pseudo-code est une simple modification de l'algorithme de Dijkstra.

    for all u in V:
   for all v in V:
      path[u][v] = infinity

for all s in V:
   path[s][s] = 0
   H = makequeue (V) .. using pathvalues in path[s] array as keys
   while H is not empty:
      u = deletemin(H)
      for all edges (u,v) in E:
         if path[s][v] > path[s][u] + l(u, v) or path[s][s] == 0:
            path[s][v] = path[s][u] + l(u,v)
         decreaseKey(H, v)

lengthMinCycle = INT_MAX

for all v in V:
   if path[v][v] < lengthMinCycle & path[v][v] != 0 :
      lengthMinCycle = path[v][v]

if lengthMinCycle == INT_MAX:
   print(“The graph is acyclic.”)

else:
   print(“Length of minimum cycle is ”, lengthMinCycle)

    Temps De La Complexité: O(|V|^3)

  3. 0
    • Effectuer DFS
    • Au cours de DFS garder la trace du type de la bordure
    • Type de bords sont Tree EdgeBack EdgeDown Edge et Parent Edge
    • Garder une trace lorsque vous obtenez une Back Edge et avoir un autre compteur pour l'obtention de la longueur.

    Voir Algorithms in C++ Part5 - Robert Sedgwick pour plus de détails

  4. 0

    Ce que vous avez à faire est de lui attribuer un autre poids à chaque nœud qui est toujours de 1. Maintenant exécuter n'importe quel plus court chemin algorithme à partir d'un nœud, le nœud à l'aide de ces poids. Mais, tout en considérant l'intermédiaire des chemins, vous devez ignorer les chemins dont les poids réels sont négatifs.

  5. 0

    Nous pouvons également utiliser branch and bound algorithme pour le problème du voyageur de commerce, comme votre question matchs avec TSP.
    http://lcm.csa.iisc.ernet.in/dsa/node187.html