Frais dommageables minimum dans le graphique

Je pense qu'un kruskal modifié est la voie à suivre ici.

Prenez le graphique g '= (v', e '), v' = v, e '= {}. Triez les bords dans E dans l'ordre de coût non croissant. Maintenant, pour chaque bord de E, ajoutez-le à E 'IFF, il ne connecte pas deux composants qui ont les deux sommets avec des bombes. Le résultat est la somme des coûts de E-E '.

EDIT:

en cours d'exécution sur votre exemple.

Initialement, notre ensemble d'arêtes est vide {}, et nous prenons les bords triés dans l'ordre non croissant [(1, 2), (0, 1), (2, 4), (1, 3)]

Donc, au début, notre graphique est composé de 5 composants déconnectés.

(1, 2) a un coût de 8, et seul l'un des composants qu'il connecte a une bombe. Nous l'ajoutons donc à E '. E '= {(1, 2)} et nous avons 4 composants.

Le bord de coût supérieur suivant est (0, 1) avec un coût de 5. Mais les deux composants ont des bombes, donc ne pas ajouter ce bord.

Le prochain est (2, 4). Cela se connecte également aux composants avec des bombes, de sorte que nous ignorons cela aussi.

Enfin, le bord de coût le plus bas est (1, 3). Étant donné qu'un de ses composants (contenant uniquement le nœud 3) n'a pas de bombe, nous l'ajoutons à E '.

Cela nous donne E '= {(1,2), (1, 3)}.

Mon raisonnement est que nous essayons d'ajouter des bords avec des coûts plus élevés avant ceux avec des coûts inférieurs - ce qui garantit que dans n'importe quel chemin entre les nœuds avec des bombes contenant des bombes dans le nœud d'origine, tout sauf le coût le plus bas sera ajouté.

Je pense que la suggestion suivante devrait fonctionner:

• 1) Commencez par une bombe, dans votre exemple, je commence par: 0
• 2) Créez des chemins sorcière tous les nœuds adjacents. Alors prenez toutes les relations et démarrez un chemin avec eux. Dans votre exemple, il lancera un chemin: 0 -> 1 .
• 3) Si vous frappez une autre bombe sur un chemin, vous retirez le bord avec le coût le plus bas. Dans l'exemple, nous ne frappons pas une bombe, nous continuons donc avec Step2.
• 3a) Pas encore de bombe dans aucun chemin. Continuez avec l'étape 2 et étendez les chemins avec les nouveaux nœuds adjacents. Dans votre cas, un nouveau chemin sera créé: 1 -> 3 . Et l'existant sera étendu: 0 -> 1 -> 2
• 3b) Une bombe se trouve sur le chemin. Prenez le chemin où la bombe est trouvée et retirez le bord avec le coût le plus bas. Dans votre exemple, le chemin 0 -> 1 -> 2 contient une bombe (2). Nous supprimons donc la relation avec le coût 5. Retirez le chemin du «TODO» et continuez par l'étape 2 sur les derniers nœuds atteints (2 et 3).

  i la fin que vous devriez traverser chaque noeud exactement une fois. Si je ne me trompe pas la complexité devrait être sur O (n journal n)