a problem similar to Graph....can somebody help me

[nonstop]

There's N vertices.
And between two vertice,there may exist path(s) or non.
each path between two vertices are not same in length.
How could I find the shortest length if these vertices construct a complete graph? in this problem,you don't need to care ablut the start and end point.Just calculate the shortest length that can connect all vertices.
Thank you for giving me some hint.

[playerX]

search google.com for floyd warshall [it's O(N^3)] or you can do better with johnson's algorithm (a bit more complicated though)...

[Larry]

Actually, this sounds like a MST problem, unless he meant that as a path, then it's either TSP or Hamiltonian Path/Cycle...

MST = Minimum Spanning Tree
TSP = Traveling Salesperson Problem..

Ya.. Google..

[nonstop]

I guess it's not MST problem.
Because there may be one or more node connect to one node.
Just let all nodes be in a connected componet.

[Maarten]

I am not sure if I understand your problem right, but to me it sounds like MST...
So what you want is: Given a connected graph, find the set of edges with minimum weight such that the graph is still connected. Am I right here ?

[nonstop]

I am not sure if I understand your problem right, but to me it sounds like MST...
So what you want is: Given a connected graph, find the set of edges with minimum weight such that the graph is still connected. Am I right here ?

"Given a connected graph, find the set of edges with minimum weight such that the graph is still connected. "
YA!That's what I meant!
Thank you.....
I supposed that each node within a spanning tree only have at most two edge connected to another node.....
am i wrong??

[rjhadley]

To find a minimum spanning tree you can use either Kruskal's or Prim's algorithms.

Note that if each vertex has at most degree of two then you have a path (or collection of paths if the graph isn't connected). But the minimum spanning tree is not necessarily a path. (Hence, it is called a "tree"!) In fact, in a minimum spanning tree the maximum degree is unbounded. (i.e. for k > 0, there exists a graph G with weight function such that the maximum degree of a vertex in the minimum spanning tree of G equals k). For example, with k = 3, consider:

V(G) = { a, b, c, d }, E(G) = { ab, ac, ad, bc, bd, cd } (i.e. complete graph on 4 vertices) and weight function w given by: w(ab) = w(ac) = w(ad) = 1 and w(bc) = w(bd) = w(cd) = 100. Then the minimum spanning tree has edges { ab, ac, ad } and deg(a) = 3.