Trouver les chemins les plus courts dans un graphique unipathique pesé

Un graphe orienté est dit unipathique si pour deux sommets et dans le graphe , il y a au plus un chemin simple de à .v G = ( V , E ) u $u$$v$$G=(V,E)$$u$$v$

Supposons que l'on me donne un graphe unipathique tel que chaque bord a un poids positif ou négatif, mais ne contient aucun cycle de poids négatif.$G$

De cela , je veux trouver un algorithme qui trouve tous les chemins les plus courts à tous les nœuds d'un nœud source .$O(|V|)$$s$

Je ne sais pas comment j'allais aborder ce problème. J'essaie de voir comment je pourrais utiliser le fait qu'il ne contient aucun cycle de poids négatif et bien sûr au plus un chemin simple entre n'importe quel nœud à .$u$$v$

Choisissez une représentation des données

Tout d'abord, regardez la taille du résultat. Vous voulez la collection des chemins les plus courts de vers tous les autres nœuds. Sauf si la longueur moyenne d'un chemin est limitée par une constante (ce qui n'est pas le cas: toute liste est unipath, et si vous prenez la racine de la longueur totale des chemins est où est la longueur de la liste), vous devrez être prudent dans votre représentation des données: la structure contenant les chemins devra utiliser le partage entre les chemins.s n ( n - 1 ) / 2 $s$$s$$n(n-1)/2$$n$

À l'exclusion des cycles, il existe un seul chemin de vers tout autre nœud . Si ce chemin passe par un nœud intermédiaire , alors le premier segment du chemin est le chemin souhaité de à . u t s $s$$u$$t$$s$$t$

Je propose de stocker le résultat dans un tableau, indexé par des nœuds numérotés de à , avec . Chaque élément du tableau stocke l'index du nœud précédent sur le chemin vers ce nœud (utilisez par exemple comme marqueur spécial pour les nœuds inaccessibles depuis ). Le chemin de à sera .| E | - 1 s = 0 - 1 s s t ( s = R [ … R [ t ] … ] , … , R [ R [ t ] ] , R [ t ] , t $0$$|E|-1$$s=0$$-1$$s$$s$$t$$(s=R[\ldots R[t]\ldots],\ldots,R[R[t]],R[t],t)$

Parcourez le graphique

Initialisez à tous .- $R$$-1$

Effectuez une traversée en profondeur ou en largeur du graphique à partir de . Chaque fois qu'un nœud est atteint, définissez sur son prédécesseur.u R [ u $s$$u$$R[u]$

Puisqu'il y a des cycles, un nœud peut être atteint plus d'une fois. Avoir indique que a déjà été visité.$R[u] \ne -1$$u$

Prouvez l'exactitude

En raison de la propriété unipathique, peu importe la façon dont nous atteignons chaque nœud, tant que nous n'avons pas terminé un cycle. Il n'y a qu'un seul chemin simple.

Prouvez la complexité

L'algorithme peut atteindre chaque nœud plus d'une fois, il n'est donc pas clair que sa complexité soit . Le travail effectué est en fait où sont les arêtes accessibles depuis la source. Plus précisément, nous atteignons un nœud plus d'une fois dans une seule circonstance: si le nœud est le premier que nous atteignons sur un cycle particulier, et dans ce cas nous l'atteignons deux fois (une fois à partir d'un chemin simple et une fois après avoir terminé le cycle ).Θ ( | E 0 | ) V $O(|V|)$$\Theta(|E_0|)$$V_0$

Eh bien. Prouvons que dans un graphe unipathique, le nombre de cycles élémentaires croît au plus linéairement avec le nombre de nœuds. (Un cycle élémentaire est un cycle qui ne contient pas de cycle plus court.) Dans la discussion suivante, je suppose que le graphique n'a pas d'arête propre (pas d'arête d'un nœud à lui-même; ces arêtes sont de toute façon non pertinentes pour la construction du chemin ).

Les graphes unipathiques peuvent avoir des cycles, mais de manière très contrainte. Ce serait bien si nous pouvions d'une manière ou d'une autre associer chaque cycle à un nœud distinct (ou au moins, un nombre limité de cycles par nœud). Les cycles peuvent-ils partager un nœud? Malheureusement oui.

Vous pouvez avoir cycles partageant tous un nœud et aucun autre nœud. Le graphique résultant est unipathique. Avec des cycles de longueur 2, il s'agit d'un motif en étoile avec un nœud central et un nombre quelconque de nœuds tels que .a a b i ∀ i , a ⇆ b $m$$a$$a$$b_i$$\forall i, a \leftrightarrows b_i$

Nous devrons donc travailler plus dur. Eh bien, essayons de le prouver par induction. Soit le nombre de nœuds dans un graphe , le nombre d'arêtes et le nombre de cycles élémentaires qui ne sont pas des auto-arêtes. J'affirme que si est unipathique et n'est pas vide alors .G # E ( G ) # C ( G ) G # C ( G ) ≤ # V ( G ) - $\#V(G)$$G$$\#E(G)$$\#C(G)$$G$$\#C(G) \le \#V(G)-1$

Pour un graphique à un ou deux nœuds, cela est évident. Supposons que l'assertion soit vraie pour tous les graphes tels que et que soit un graphe unipathique avec nœuds. Si n'a pas de cycle, , le dossier est clos. Sinon, soit un cycle élémentaire.$\#V(G) < n$$G$$n$$G$$0 = \#C(G) < \#V(G)$$(a_1,\ldots,a_m)$

Réduire le cycle: soit le graphe dont les nœuds sont ceux de moins plus un nœud et dont les arêtes sont toutes les arêtes de n'impliquant pas les , plus chaque fois que et chaque fois que . Chaque chemin dans induit un chemin dans (si le chemin implique , alors remplacez-le par$G'$$G$$\{a_1,\ldots,a_m\}$$a$$G$$a_i$$a \rightarrow_{G'} b$$\exists i, a_i \rightarrow_G b$$b \rightarrow_{G'} a$$\exists i, b \rightarrow_G a_i$$G'$$G$$b \rightarrow a \rightarrow c$$b \rightarrow a_i \rightarrow a_{i+1} \rightarrow \ldots \rightarrow a_j \rightarrow c$ en ). Par conséquent est unipathic. De plus, comme les cycles de ne partagent pas d'arêtes, a tous les cycles de exception de celui que nous avons éliminé: . Par induction, . Puisque , nous avons .$G$$G'$$G$$G'$$G$$\#C(G') = \#C(G)-1$$\#C(G') \le \#V(G')-1$$\#V(G') = \#V(G) - m + 1$$\#C(G) = \#C(G')+1 \le \#V(G) - m = n-m \le n-1$

Ceci conclut la preuve. La traversée suit au maximum arêtes.$2|V|-2$