CODEWITHSUNDEEP
algorithm
Svisstack
Svisstack

Reputation: 16656

Smallest sum of graph weight, where each node are connected (like a network)

What algorithm I can use for problem like this:

Have a graph positive weighted, i want to know a smallest possible sum of weights where each node are connected (connected like a network, where each node is a eg. network device).

In this network each node can be connected with other node by some other other nodes in way. But all nodes from input graph must be in a network.

Upvotes: 0

Views: 279

Answers (2)

Michael Williamson
Michael Williamson

Reputation: 11438

I believe the resulting network you want is a minimum spanning tree, which has two well-known algorithms: Kruskal's and Prim's.

Upvotes: 3

Keith Randall
Keith Randall

Reputation: 23265

You're looking for a minimum spanning tree (MST).

Upvotes: 1

Related Questions