i have another qeustion..
Suppose you have many computers and you want to know the shortest length of a wire to connect them and make a network. Can this problem be solved with Dijkstra?
Dijkstra's algorithm question
Quote:Original post by valla2
i have another qeustion..
Suppose you have many computers and you want to know the shortest length of a wire to connect them and make a network. Can this problem be solved with Dijkstra?
That's called a "minimum spanning tree". That's definately not what Dijkstra's algorithm is for.
Google for "minimum spanning tree", in combination with either "Prim" or "Kruskal", which are the most used algorithms for that problem.
Author
oh... i thought the problem i described was the travelling salesperson problem because each computer can be thought as a town and the wires are the roads. It is not becuase you don't know where to start "travelling" from?
Travelling Salesman is if you need the network to be a cycle, so that when every computer is connected to exactly two others, and if you follow it in the same direction long enough you end up at the one you started.
If you only need there to be a path from every computer to every other computer with a minimal amount of wire, it's Minimum Spanning Tree (which is much easier to generate).
If you only need there to be a path from every computer to every other computer with a minimal amount of wire, it's Minimum Spanning Tree (which is much easier to generate).
Author
and that means that the 2 algorithms ( the one for TSP and the other for MST ) are very different? :(
thank you Urxae
thank you Urxae
Well, since there are widely known efficient algorithms for MST, but there is no known (to the general public anyway) efficient algorithm for TSP (despite there being a million-dollar prize for the person who finds and publishes one), they're probably rather different.
However, IIRC, one or both of Prim's and/or Kruskal's is rather similar to Dijkstra's. I'm not sure though, it's been almost two years since I took that class.
However, IIRC, one or both of Prim's and/or Kruskal's is rather similar to Dijkstra's. I'm not sure though, it's been almost two years since I took that class.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
