A problem with graphs

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

  1. ilman
    OP

    ilman Gbatemp's Official Noise Eraser

    Member
    1,130
    243
    Jul 25, 2010
    Shibuya
    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. Jamstruth

    Jamstruth Secondary Feline Anthropomorph

    Member
    3,456
    185
    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. ilman
    OP

    ilman Gbatemp's Official Noise Eraser

    Member
    1,130
    243
    Jul 25, 2010
    Shibuya
    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.