graphique - Comment trouver le Minimum Dirigé Cycle (minimum de poids total)?

Voici un accise:

Soit G un graphe orienté pondéré avec n sommets et m arêtes, où tous les côtés positifs de poids. Un tel cycle est un chemin orienté qui commence et se termine à la même sommet, et contient au moins une arête. Donner un O(n^3) l'algorithme pour trouver un dirigé cycle dans G de minimum de poids total. Partielle de crédit ne sera accordé pour une O (n^2)*m) de l'algorithme.

Voici mon algorithme.

Je fais un DFS. Chaque fois quand je trouve un back edge, je sais que j'ai dirigé cycle.

Alors je vais passer temporairement en arrière le long de la parent array (jusqu'à ce que je voyage à travers tous les sommets dans le cycle) et de calculer les total weights.

Puis-je comparer les total weight de ce cycle avec min. min prend toujours le minimum de poids total. Après le DFS finitions, notre minimum dirigé cycle est également constaté.

Ok, puis sur la complexité du temps.

Pour être honnête, je ne sais pas la complexité du temps de mon algorithme.

Pour DFS, la traversée prend O(m+n) (si m est le nombre d'arêtes, et n est le nombre de sommets). Pour chaque sommet, il pourrait point de retour pour l'un de ses ancêtres et constitue ainsi un cycle. Lorsqu'un cycle est trouvé, il faut O(n) pour résumer le poids total.

Donc je pense que le temps total est O(m+n*n). Mais c'est évidemment faux, comme indiqué dans l'accise, le moment optimal est de O(n^3) et le temps normal est de O(m*n^2).

Quelqu'un peut m'aider avec:

  1. Est mon algorithme correct?
  2. Qu'est-ce que la complexité du temps si mon algorithme est correct?
  3. Est-il un meilleur algorithme pour résoudre ce problème?
  • Il n'est pas clair ce que vous demandez de l'aide avec. Êtes-vous poser pour vous aider à déterminer votre temps de la complexité?
  • Ok, j'ai édité ma question
  • Votre algorithme est incomplète. Que faites-vous si vous rencontrez un sommet qui vous l'avez déjà vu?
  • 3in1 question 🙂
InformationsquelleAutor Jackson Tale | 2012-05-04
  1. 20

    Vous pouvez utiliser De Floyd-Warshall algorithme ici.

    La Floyd-Warshall algorithme trouve le chemin le plus court entre toutes les paires de sommets.

    L'algorithme est alors très simple, rendez-vous sur toutes les paires (u,v), et trouver la paire qui réduit au minimum la dist(u,v)+dist(v,u), depuis cette paire indique sur un cycle de u à u avec le poids dist(u,v)+dist(v,u). Si le graphique permet aussi de soi-boucles (une arête (u,u)) , vous aurez aussi besoin de vérifier eux seuls, parce que ces cycles (et seulement eux) n'ont pas été vérifiées par l'algorithme.

    pseudo-code:

    run Floyd Warshall on the graph
min <- infinity
vertex <- None
for each pair of vertices u,v
    if (dist(u,v) + dist(v,u) < min):
           min <- dist(u,v) + dist(v,u)
           pair <- (u,v)
return path(u,v) + path(v,u)

    path(u,v) + path(v,u) est en fait le chemin qui se trouve à partir de u à v, puis de v à u, ce qui est un cycle.

    L'algorithme moment de l'exécution est O(n^3), depuis de floyd-warshall est le col de la bouteille, depuis la boucle O(n^2) temps.

    Je pense que l'exactitude ici, c'est trivial, mais laissez-moi savoir si vous êtes en désaccord avec moi et je vais essayer d'expliquer mieux.

    • Merci. Je crois que votre proposition est correcte, même si je suis encore à essayer de comprendre. Je comprends algorithme de Floyd et il vous trouve toutes les paires de plus court chemin. Donc au final, nous obtenons une matrice de cotation la plus courte de poids entre toutes les paires. Et puis pour savoir qui a le minimum de poids total, nous ne pouvons la matrice de nouveau. Si la matrice[i][j] != MAX_INT et de la matrice[i][j] != MAX_INT, alors i et j de cycle et le total = matrice[i][j]+de la matrice[j][i], alors on peut trouver le minimum de l'un, ai-je le droit? Pour enregistrer la structure du cycle, nous devons utiliser un autre parent de la matrice, à droite?
    • Vous avez raison, il faut aussi souligner mon edit: cette solution ne permet pas de prendre soin de soi boucles (sur les bords comme (u,u)), de sorte que si ceux-ci sont autorisés dans le graphique, il doit être vérifié en plus (c'est facile). Notez qu'une fois que vous avez trouvé que la paire est nécessaire, vous pouvez utiliser dijkstra ou BF de u pour trouver le chemin u->...->v, puis à nouveau à partir de v pour trouver v->...->u, sans modification de la complexité de l'algorithme, afin d'obtenir le chemin d'accès réel n'est pas un problème pour ce problème.
    • Très clair, Merci bien @amit
    • Quel est le problème avec la dist(u,u)? Si ce n'est pas la longueur du cycle le plus court u→...→u (y compris les boucles), doivent être parler de différents Floyd-Maréchals?
    InformationsquelleAutor amit
  2. 2

    "Pour chaque sommet, il pourrait point de retour pour l'un de ses ancêtres et constitue ainsi un cycle de"

    Je pense qu'il pourrait point de retour pour l'un de ses ancêtres qui signifie N

    Aussi, comment sont-u va marquer des points quand vous êtes sortis de son dfs, vous pouvez y venir à nouveau à partir d'autres vertex et sa va être un autre cycle. Ce n'est donc pas (n+m) dfs plus.

    1. So ur algo est incomplète
    2. même ici

    3.
    Lors d'un dfs, je pense que le sommet devrait être invisible, ou vérifier, et pour les u peut stocker le poids minimum pour le chemin d'accès au sommet de départ. De sorte que si à un autre moment u trouver un avantage à ce sommet u de ne pas avoir à la recherche de ce chemin plus.
    Cette dfs va trouver le minimum dirigé cycle contenant du premier sommet. et c'est O(n^2) (O(n+m) si u stocker le graphe sous forme de liste)

    Donc, si à n'importe quel autre sommet, ça va être O(n^3) (O(n*(n+m))

    Désolé pour mon anglais et je ne suis pas bon à la terminologie

    InformationsquelleAutor Herokiller
  3. 2

    Est mon algorithme correct?

    Pas. Permettez-moi de donner un contre-exemple. Imaginez que vous commencez à DFS de u, il y a deux chemins p1 et p2 de u à v et 1 chemin p3 de v retour à u, p1 est plus courte que p2.

    Supposons que vous commencez par prendre le p2 chemin à v, et retour à pied u par voie p3. Un cycle de trouvé mais apparemment ce n'est pas minimale. Ensuite, vous continuez à explorer u en prenant le p1 chemin, mais depuis v est entièrement exploré, le DFS se termine sans trouver le minimum du cycle.

    • Pour plus de lisibilité, vous devez utiliser le format de code en l'entourant de vos noms de variables avec des backticks comme "ceci"
    • Merci pour vos conseils. Mis à jour.
    InformationsquelleAutor shuais
  4. 0

    J'ai fait le même genre de chose, mais je n'ai pas tout visité tableau pour dfs (ce qui était nécessaire pour mon algorithme fonctionne correctement), et donc j'ai réalisé que mon algorithme est de complexité exponentielle.

    Depuis, vous êtes à la recherche de tous les cycles, il n'est pas possible de trouver tous les cycles en moins de temps exponentiel car il peut y avoir 2^(e-v+1) cycles.

    InformationsquelleAutor B RAGHUNATHAN