Comment trouver le chemin le plus court qui couvre tous les nœuds d'un graphe cyclique dirigé?

Question

J'ai besoin d'un exemple du plus court chemin d'un graphe cyclique dirigé d'un noeud (il devrait atteindre tous les nœuds du graphe à partir d'un noeud qui sera l'entrée).

S'il vous plaît s'il y a un exemple, j'en ai besoin en C++, ou l'algorithme.

Answer 1

EDIT: Oups, mal lu la question. Merci @jfclavette d'avoir choisi ça. La vieille réponse est à la fin.

Le problème que vous essayez de résoudre s'appelle le Travelling salesman problem. Il y a beaucoup de potential solutions, mais c'est NP-complet donc vous ne pourrez pas résoudre les grands graphiques.

ancienne réponse:

Qu'est-ce que vous essayez de trouver est appelé girth d'un graphe. Il peut être résolu en définissant les distances d'un nœud à lui-même à l'infini et en utilisant l'algorithme Floyd-Warshall. La longueur du plus court cycle à partir du nœud i est alors juste l'entrée en position ii.

Answer 2

Pour un graphe non pondéré, BFS fera le travail. Comme il y a un cycle potentiel dans votre graphique, vous devez garder une trace du nœud visité (vous avez en quelque sorte besoin de le faire pour BFS de toute façon).

Pour le graphe pondéré, l'algorithme de bellman-Ford peut être utilisé. Il est également capable de détecter les cycles.

Answer 3

Dans le cas non pondéré: Breadth first search. Dans le cas pondéré: Dijkstra's.

Answer 4

En pseudocode:

//INPUT: graph G = (V,E) 
//OUTPUT: shortest cycle length 
min_cycle(G) 
    min = ∞ 
    for u in V 
    len = dij_cyc(G,u) 
    if min > len 
     min = len 
    return min  

//INPUT: graph G and vertex s 
//OUTPUT: minimum distance back to s 
dij_cyc(G,s) 
    for u in V 
    dist(u) = ∞ 
        //makequeue returns a priority queue of all V 
    H = makequeue(V) //using dist-values as keys with s First In 
    while !H.empty? 
    u = deletemin(H) 
    for all edges (u,v) in E 
     if dist(v) > dist(u) + l(u,v) then 
     dist(v) = dist(u) + l(u,v) 
     decreasekey(H,v) 

    return dist(s) 

Cela va une années Dijkstra légèrement différentes sur chaque sommet. Le Dijkstras muté a quelques différences clés. Tout d'abord, toutes les distances initiales sont définies sur ∞, même le sommet de départ . Deuxièmement, le sommet de départ doit d'abord être mis dans la file d'attente pour que le résultat soit le premier, car ils ont tous la même priorité. Enfin, le Dijkstras muté renvoie la distance au nœud de départ. S'il n'y avait pas de retour au point de départ , la distance reste ∞. Le minimum de tous ces retours des Dijkstras mutés est le chemin le plus court. Puisque Dijkstras court au pire dans O (| V |^2) et que min_cycle court cette forme de Dijkstras | V | fois, le temps final pour trouver le cycle le plus court est O (| V |^3). Si min_cyc renvoie ∞ alors le graphe est acyclique.

Pour retourner le chemin réel du cycle le plus court, seules de légères modifications doivent être effectuées.