Poids Négatif Du Cycle De L'Algorithme De

Je pensais à propos de l'algorithme de recherche d'un poids négatif cycle dans un graphe orienté. Le Problème est que nous avons un graphe G(V,E), nous avons besoin de trouver un algorithme efficace pour trouver un cycle de poids négatif. Je comprends l'algorithme dans ce document PDF

Brièvement, l'algorithme est l'application de Bellman Ford par l'algorithme d'itération |V|-1 fois relaxations. Ensuite, il vérifie si il existe une arête qui peut être encore plus détendue, puis un cycle de poids négatif existe et on peut le faire remonter par la société mère de pointeurs et tout se passe bien, nous trouvons un cycle de poids négatif.

Cependant, je pensais à un autre algorithme de simplement en utilisant la profondeur de la première recherche (DFS) sur le graphique en gardant la trace de la somme de la distance parcourue, je marque tous les nœuds blancs au début et à la rendre gris quand je suis à la recherche d'un chemin, et de les marquer noir quand ils sont finis, je sais que je trouve un cycle si et seulement si je trouve un nœud visité et il est gris (mon chemin) , pas noir qui était déjà terminée par la Profondeur d'Abord de recherche, et donc pour mon algorithme, si j'atteins un gris nœud qui a déjà été visité, je vérifie qu'en serait-il de mise à jour (la distance) et si il est plus bas qu'avant, je sais que j'ai un cycle de poids négatif et peut remonter.

Est mon algorithme de mal? Si oui, pouvez-vous trouver un contre-exemple ? Si non pouvez-vous m'aider à le prouver?

Merci

Afin de trouver un -ve cycle, les algorithmes comme ce doit le traverser. Je soupçonne que, dans un grand graphe, il existe un très grand nombre de cycles. Dans un graphe connexe à N nœuds, il y aura N!/N cycles, à commencer par le premier nœud et de visiter chacun des autres nœuds. Donc je pense que votre algorithme doit prendre beaucoup plus de temps que de Bellman-Ford ou de manquer certains cycles dans certains graphiques.
faites-vous dfs à partir de chaque nœud? si non, quels sont les nœuds de commencer la recherche de?
mon dfs parcouru tous les nœuds, quand il est coincé, il trouve un autre nœud avec 0 en degrés et ne dfs de nouveau. Dans l'ensemble, mon DFS doit s'exécuter en O(V+ E) temps (linéaire)

OriginalL'auteur Saher Ahwal | 2011-04-04

  1. 3

    Un problème, vous êtes le marquage des nœuds. 

     A <--->   B
 |         ^ 
   \--\    |  
           v    
       ->  D  (crap ascii art, A  connects to D unidirectionally)

    Supposons que vous prenez le chemin A->B->D, A B D sont gris quand vous frappez D. Aucun cycle n'est trouvé. Vous pop de A; B et D sont de couleur noire. Vous prenez le bord, aucun cycle n'est trouvé, parce que D est noir.

    En général, le nombre de chemins est exponentiel en la taille du graphe. Vous devriez essayer tous les chemins, il n'y a aucun moyen de marquer les nœuds ici. Si vous avez traité bord de la direction dans le graphe orienté séparément, je crois que vous seriez en mesure de faire ce marquage les bords, cependant, c'est l'équivalent de l'énumération de tous les chemins.

    OriginalL'auteur dfb

  2. 16

    Bellman Ford ne fonctionne pas toujours, le problème est de son un source unique chemin le plus court algorithme, si le négatif de la boucle n'est pas accessible à partir de la source que vous choisissez, il échoue. Cependant, un peu de changement de Bellman Ford pourrait aider, au lieu de sélectionner une source de vertex et initialiser sa distance à 0, on peut initialiser la distance à 0, puis exécutez de Bellman Ford. C'est l'équivalent d'ajouter un supplément de sommet s' qui pointe vers tous les points dans le graphique d'origine avec 0 poids bord. Une fois de Bellman Ford est exécuté sur le graphique et nous avons trouvé tout sommet u et arête (u,v) d[u] + w[u][v] < d[v], nous savons qu'il doit être un cercle vicieux conduisant à u, suivi de retour à partir de u dans la prédécesseur graphique et nous allons trouver le cycle.

    DFS n'est pas va fonctionner en aucune façon, il n'est évidemment pas en mesure d'épuiser tous les possibles cycles. DFS peut être utilisé pour rechercher la présence de cycle dans le graphe, mais pas plus.

    Pourriez-vous en dire plus sur le suivi de retour? Le cycle de trouvé via le suivi de retour doit être le cycle négatif? La Dose moyenne, si d[u] + w[u][v] < d[v] n'est pas satisfait, alors il n'y a pas de cycle dans la prédécesseur graphique?
    Le prédécesseur graphique a un bord de chaque vertex. Tout graphe ayant n sommets ont un cycle, de sorte que le prédécesseur graphique a un cycle. Et BF ne produit jamais de positif cycles, nous sommes donc assurés de trouver un cycle négatif.

    OriginalL'auteur shuais

  3. -1

    Je crois qu'il existe une façon de résoudre ce problème en temps linéaire.
    Tout en recherchant le graphique avec la profondeur de la première recherche (DFS a un temps d'exécution de O(V+E)), vous pouvez garder une trace de la distance de la source vers le nœud courant (par simplement incrémenter le parent de la distance avec le poids de l'arête reliant le nœud enfant à la mère).
    Ensuite, chaque fois que vous rencontrez un cycle (cycles sont découverts à travers la recherche d'un bord arrière dans un graphe non-dirigé, soit d'un bord ou d'un attaquant de pointe dans un graphe orienté), vous pouvez soustraire la distance entre le nœud source et le nœud racine du cycle de la distance entre le nœud source et le nœud final dans le cycle (le nœud racine étant le nœud où le cycle a commencé).
    Si le résultat est négatif, le cycle doit être négatif!

    OriginalL'auteur JMS