Je rencontre des problèmes pour résoudre un problème concernant Minimum Spanning Tree. Ainsi, chaque nœud d'un graphique est une ville, et il est possible d'avoir des limites de poids reliant deux nœuds, ce qui représente le coût de construction d'une route entre deux villes. Le problème consiste essentiellement à dire le coût minimum de la construction des routes et de connecter toutes les villes. Je peux facilement résoudre ceci en utilisant l'algorithme Prim ou kruskal pour résoudre ce sous-problème de mon plus gros problème. La partie difficile vient maintenant: Chaque ville (nœud) peut avoir un aéroport et chaque aéroport a un coût ponctuel (si vous décidez de le construire). Vous pouvez voyager entre deux villes en utilisant un aéroport si les deux villes ont des aéroports. Maintenant, je dois calculer le coût minimum de la construction des routes et des aéroports afin d'avoir toutes les villes connectées, mais j'ai du mal à représenter les connexions avec les aéroports avec le reste du réseau. Quelqu'un peut-il m'aider ici? Peut-être que je me trompe complètement à propos de l'utilisation de MST?Arbre Spanninjg minimum avec poids de sommet et poids de bord
La seule solution que j'ai trouvée est: Pour chaque ville qui a un aéroport, je vais connecter cette ville avec d'autres villes qui ont des aéroports. Aussi Si le coût de la construction de deux aéroports est inférieur à la construction d'une route, je le prends en considération. Je cours kruskal afin d'obtenir le bord le moins cher, mais si kruskal choisit un bord "d'aéroport", je l'ajouterai au spanning-tree et puis au coût des deux aéroports (s'ils ont été construits dans le passé). Je crois qu'en faisant ce changement dynamique de poids en courant kruskal, je détruis l'idée d'obtenir le coût minimum.
+1. FWIW, je peux confirmer que votre algorithme ne donnera pas des résultats corrects dans tous les cas: considérons trois villes, où le coût de construction d'un aéroport dans une ville est de 3 et le coût de construction d'une route entre deux villes est de 5 le coût est de construire trois aéroports et pas de routes (coût total = 3 + 3 + 3 = 9), mais la construction d'aéroports dans deux villes coûte plus cher que la construction d'une route entre eux (coût = 3 + 3 = 6 vs. = 5), votre algorithme ne construirait aucun aéroport, donc il construirait plutôt deux routes (coût total = 5 + 5 = 10), ce qui n'est pas optimal. – ruakh