How to efficiently construct a connected graph?

Question

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

Answer 1

See Minimum Spanning Tree algorithms.

Answer 2

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

Answer 3

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).

Answer 4

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.