Dijkstra mit Flughäfen und Straßen

Question

Ich denke darüber nach, wie ich ein Problem lösen könnte, Städte zu verbinden. Ich muss entscheiden, in welchen ich Flughäfen oder Straßen bauen würde. Ich stellte mir vor, dass ein Graph diese Situation darstellen könnte. Die Eckpunkte wären die Städte mit einem Gewicht, das den Preis eines Flughafens symbolisiert und die Kanten die Straßen mit ebenfalls einem Gewicht. Ziel ist es, alle Städte mit dem Netzwerk zu verbinden und so die Gesamtkosten der Arbeiten zu minimieren. Ich denke, eine Adaption von Dijkstra algoritm würde mir den günstigsten Preis geben, wo das Gesamtgewicht eines Scheitelpunktes seine Grundkosten plus die Randkosten sind. Ich bin in der Argumentationsphase, also ist jeder Tipp oder Hinweis dankbar.

Answer 1

Ich denke, es ist über Mindest Spanning Tree Frage ...
So Kruskal oder prim Algorithmus ist ok ...
Dijkstra über den kleinsten Weg ist, wenn Sie Punkt wissen beginnen ..
wünschen dies helfen kann, Sie.