# A problem with graphs

Discussion in 'Computer Programming, Emulation, and Game Modding' started by ilman, Oct 27, 2013.

# A problem with graphs

554 Views
1. ### ilmanGbatemp's Official Noise Eraser

Member
Jul 25, 2010
Hello, 'Temp.
I've been stuck on this problem for 2 hours or so without any ideas...
The way it goes is that you have an unoriented multi-graph with N vertices and M links between them.
Each link has its own length.
Every combination of vertices has a number of Xs(let's call 'em that) wanting to get from the first vertex to the second and from the second to the first.
You need to choose N-1 of these M links, so that both of these conditions are met:
1. There is a way to get from any vertex to all others. (easy as pie)
2. The links need to be chosen in such a way that the travelled distance of all Xs is minimal in comparison to all other combinations.

I've already solved it via DFS (Depth-First Search), but it's just too slow.
I know there is a faster method, but I can't think of it for the likes of me.

If anyone can post a solution, I'll be extremely thankful.
Just saying that this must be written in C++.

And to those who might be asking: No, this is not homework.

2. ### JamstruthSecondary Feline Anthropomorph

Member
Apr 23, 2009
North East Scotland
So you need to make a Minimum Spanning Tree. I think what you need here is an algorithm called Dijkstra's Algorithm. http://en.wikipedia.org/wiki/Dijkstra's_algorithm Wikipedia even has some Pseudocode there for you.

If you can figure out some way of ordering your Nodes and Edges in the array that you don't have to search through to find them every time it would speed things up as well. E.g. Each node has an ID number. It's stored in the array at that Index.

3. ### ilmanGbatemp's Official Noise Eraser

Member
Jul 25, 2010
I am fully aware of how Dijkstra's algorithm and Minimum Spanning trees work. And I can only see how the tree will help me.
And I am ordering everything the fastest way possible.
There is some other faster algorithm. I'm sure of it.