Thread: Graphs

  1. #1
    Registered User
    Join Date
    Jun 2007
    Posts
    2

    Graphs

    Hi all!!

    If i have a number of routers connected by internet lines (with speed associated as weight)- oriented graph - and need to calculate a "path" between routers that:

    1. Allows a router to send messages to any another router (it can cross other routers)
    2. Have the minimum number of elements possible
    3. Maximize the sum of speeds in the lines.

    What graph algorithms should i use? Any ideas?


    Thanks

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    What choices have you considered so far ?

    http://www.nist.gov/dads/, use the local search for "graph" and see what you can come up with in terms of an algorithm.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jun 2007
    Posts
    2
    Thanks for the link, i'll take a look at it.

    I'm inclined for the ford-fulkerson algorithm but i'm not sure...

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Why do I get the feeling that this is an attempt to disguise homework?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > I'm inclined for the ford-fulkerson algorithm but i'm not sure
    Sounds like a good plan to me.

    Even if it turns out to be wrong, you'll learn a lot more about the problem.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Graphs and the STL
    By smitsky in forum C++ Programming
    Replies: 1
    Last Post: 12-04-2004, 06:32 PM
  2. graphs and algorithms
    By Micko in forum C++ Programming
    Replies: 1
    Last Post: 04-26-2004, 01:13 PM
  3. Generate Graphs
    By beet in forum C Programming
    Replies: 6
    Last Post: 08-19-2003, 07:14 PM
  4. graphs
    By cmpcnic1@livjm. in forum C++ Programming
    Replies: 3
    Last Post: 03-19-2003, 07:06 AM
  5. graphs
    By res025ol in forum C++ Programming
    Replies: 0
    Last Post: 03-28-2002, 08:31 PM