Modification de l'algorithme de Dijkstra pour les poids de bord tirés de la plage

Supposons que j'ai un graphique dirigé avec des poids de bord tirés de la plage $[1,\dots, K]$ où $K$ est constant. Si j'essaie de trouver le chemin le plus court en utilisant l'algorithme de Dijkstra , comment puis-je modifier la structure de l'algorithme / des données et améliorer la complexité temporelle en $O(|V|+|E|)$ ?

algorithms data-structures shortest-path weighted-graphs user1675999
la source

Vous devriez être plus précis, quelle est votre structure de données? Et vous ne pouvez pas obtenir moins d'

. Revoir les conférences.

O (V + E)

$O(V+E)$

jonaprieto

Ce n'est pas parce que les possibilités de poids de bord distincts sont petites que le nombre de distances est petit.

Joe

Commencez par colorier les sommets de votre graphique en bleu, puis subdivisez chaque bord de taille

en bords

(en ajoutant

sommets non colorés), puis exécutez le BFS sur ce nouveau graphique, pour trouver les chemins les plus courts du nœud de départ aux nœuds bleus, c'est

si vous avez une constante

t

$t$

t

$t$

t - 1

$t-1$

O (| V | + | E |)

$O(|V|+|E|)$

k

$k$

@SaeedAmiri pourquoi ne pas écrire cela comme une réponse?

Joe

@Joe parce qu'il ne modifie pas dijkstra (au moins directement n'est pas lié à dijkstra).

Réponses:

Si les poids de bord sont des entiers dans , vous pouvez implémenter Dijkstra pour qu'il s'exécute en $\{0,1,\ldots,K\}$ $O(K|V|+|E|)$ , en suivant la suggestion de @ rrenaud. Voici une explication plus explicite.

À tout moment, les clés (finies) de la file d'attente prioritaire sont dans une certaine plage , où est la valeur de la dernière clé retirée de la file d'attente prioritaire. (Chaque clé est au moins , car la séquence de clés supprimée par l'algorithme de Dijkstra n'est pas décroissante, et chaque clé est au plus , car chaque clé a la valeur pour un bord $\{D,D+1,\ldots,D+K\}$ $D$ $D$ $D+K$ $d[u] + wt(u,w)$ $(u,w)$ où est la distance de la source à un sommet qui a déjà été supprimé, donc $d[u]$ $u$ $d[u]\le D$ )

Pour cette raison, vous pouvez implémenter la file d'attente prioritaire avec un tableau circulaire de taille , chaque cellule contenant un compartiment. Stockez chaque sommet avec la clé dans le seau dans la cellule où . Gardez une trace de $A[0..K]$ $K+1$ $k$ $A[h(k)]$ $h(k)=k \bmod (K+1)$ $D$ . Effectuez les opérations comme suit:

delete-min : Alors que est vide, incrément . Ensuite, supprimez et renvoyez un sommet de $A[h(D)]$ $D$ $A[h(D)]$ .
insérer avec la clé : ajouter le sommet au seau de $k$ $A[h(k)]$ .
touche décroissante à : déplacer le sommet de à $k$ $k'$ $A[h(k)]$ $A[h(k')]$ .

L'insertion et la diminution de la clé sont des opérations à temps constant, donc le temps total passé dans ces opérations sera . Le temps total passé en suppression min sera ainsi que la valeur finale de . La valeur finale de est la distance maximale (finie) de la source à tout sommet (car une suppression-min qui prend itérations augmente de ). La distance maximale est au plus $O(|V|+|E|)$ $O(|V|)$ $D$ $D$ $i$ $D$ $i$ $K(|V|-1)$ car chaque chemin a au plus bords. Ainsi, le temps total passé par l'algorithme est . $|V|-1$ $O(K|V|+|E|)$

Neal Young
la source

J'aime la file d'attente circulaire, c'est bien mieux que mon idée d'avoir essentiellement un tableau de taille K * v où seule une tranche de taille av est utilisée à un moment donné.

rrenaud

Je l'ai implémenté à l'aide d'une double liste chaînée, cela signifie-t-il toujours que c'est O (1) pour trouver la clé min?

user1675999

@ user1675999, je ne suis pas sûr. si votre liste est triée par clé, comment insérez-vous et diminuez-vous efficacement la clé? si votre liste n'est pas triée par clé, comment faire pour supprimer-min efficacement?

Neal Young

Je suppose ici que est un entier et que les poids des bords sont intégraux. Sinon, cela ne vous achète vraiment rien, vous pouvez toujours redimensionner les poids de sorte que le bord minimal ait coûté et le maximum a coûté $K$ $1$ $K$ , de sorte que le problème est identique au problème de chemin le plus court standard.

Algorithme / esquisse de preuve: implémentez la file d'attente prioritaire de cette manière folle comme un tableau de listes indexées par coût et utilisent autrement l'algorithme de Dijkstra standard. Gardez un compteur qui suit le coût de l'article minimum dans le tas. Résolvez l'appel de mise en file d'attente une fois les éléments supprimés par balayage linéaire . Oui, ce genre de sons semble fou, mais constant $K\times |V|$ $K$ vous permet de tricher et de tromper votre intuition algorithmique contre les analyses linéaires. Il vous suffit de numériser à partir du dernier marqueur min car l'algorithme de Disjkstra est agréable pour votre implémentation de file d'attente. Au moment où il demande une mise en file d'attente, les éléments insérés dans la file d'attente sont toujours supérieurs ou égaux au minimum précédent. Le plus long chemin le plus court possible a une longueur, votre coût de numérisation amorti est donc si K est constant. $K\times |V|$ $K\times |V| = O(|V|)$

rrenaud
la source

-2

vous pouvez utiliser le tri topologique pour trouver la solution, laisser la source avoir le degré 0, aller de chaque bord de la source, si un autre sommet a 0 degré, le mettre dans la file d'attente et continuer à le faire. dans ce cas (sans cycle à l'intérieur du graphique), il peut atteindre V + E car il traverserait chaque sommet et chaque arête une seule fois.

TIANYANG ZHANG
la source

Semble sans rapport avec la question? La question ne suppose pas que le graphique est acyclique, et votre solution n'utilise pas le fait que les poids sont tirés d'une plage constante.

xskxzr