Algorithme Prim optimisé pour les poids de bord connus?

Question

Comment pouvez-vous modifier l'algorithme de prim dans le cas où vous connaissez déjà la valeur minimale d'un poids donné? Par exemple, si un graphe est constitué de poids de bord 0 et 1, comment pouvez-vous accélérer l'algorithme de prim?

Answer 1

La première stratégie semble améliorer la file d'attente prioritaire pour tirer parti de vos données. Si vous savez que les poids sont des valeurs discrètes inférieures à C, vous pouvez remplacer le tas binaire généralement utilisé par un tas de base. De cette façon, vous pouvez facilement obtenir la même complexité algorithmique qu'avec le tas de Fibonacci beaucoup plus difficile à implémenter, ou peut-être même mieux. L'algorithme de Dijkstra utilise exactement les mêmes structures de données et est ici une explication détaillée de la façon de mettre en œuvre un tas de radix pour elle:

http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/spalgs/radixheap.txt

Exemple de code radixheap.cpp se trouve ici:

http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/spalgs/spalgs.html

Vous pouvez simplement appliquer la même structure de données à l'algorithme de Prim que ce texte explique pour l'algorithme de Dijkstra, pour obtenir la complexité O (m + n log C) où m est arêtes, n est sommets et C est le poids maximum. Si vos poids de bord ne sont que de petits entiers, c'est très bien. Pour résumer l'idée du segment de base, les éléments sont placés dans des compartiments en fonction de leur priorité (qui doit être un nombre entier). La plage de valeurs couverte par le godet N est approximativement de taille 2^N, donc trouver le godet adéquat est proportionnel au log du plus grand nombre possible. Lors de l'extraction de l'élément avec la plus petite priorité, les éléments sont parfois redistribués dans des compartiments inférieurs, ce qui entraîne une complexité logarithmique.

Si vous vouliez dire que les poids de bord sont des nombres à virgule flottante arbitraires compris entre 0 et 1, cela n'autorise aucune optimisation. Évidemment, n'importe quel graphique peut être transformé en divisant tous les poids de bord par le poids maximum de bord, les rendant tous entre 0 et 1. Cette transformation ne peut pas faire fonctionner l'algorithme de Prim plus rapidement. Vous pouvez transformer toutes les arêtes en ajoutant le même nombre à toutes les arêtes, ou en les multipliant avec le même nombre positif, sans modifier le résultat du tout.