How to efficiently construct a connected graph?

For fun I'm learning about graph theory and I came across this problem. Given a set of vertices V, a set of edges E, and a weight for each edge in E, how can I efficiently construct a graph G such that:

• G is connected (all vertices are connected via some path)
• the sum of the weights of the edges is minimized

Cheers!

Edit: the edges in E are directed, when all edges in E are present there can be cycles

From stackoverflow

• See Minimum Spanning Tree algorithms.

• Read Bellman-Ford Algorithm. It supports negative weight cycles. Dijkstra's algorithm is more efficient but it doesn't support negative weight cycles.

  John Fouhy : Those are single-source shortest path algorithms -- not what the OP is after.

  Faran Shabbir : What is he after? Can u please tell me if some MST algorithm allow cycles?

• To add to ars's answer, if your graph contains edges with negative weight, then the problem becomes more difficult (and there may be no solution if you have a negative-weight cycle).

• ok... can i know what MrDatabase is after? SSSP algorithms (dijkstra, Bellman-Ford) are variation of MST, which ars just mentioned. Dijkstra does not solve negative weight cycle issue while Bellman-Ford does.

  redtuna : MSP does not always give the same solution as SSSP. Negative weight cycles are not a problem in MSP since we're just minimizing the sum of the edge weights.

  Faran Shabbir : "Edit: the edges in E are directed, when all edges in E are present there can be cycles" it is mentioned in the question. MST is for acyclic graphs, we can't use MST, Prim's, Kruskel or other MST algos for this problem. We can use Bellman-Ford for negative cycles and Dijkstra for positive cycles. Yes SSSP can start from a particular node but tell me about some MST algorithm which can allow cycles?