Shortest path problem for undirected graph, with no weights per edge

This is a discussion on Shortest path problem for undirected graph, with no weights per edge within the Tech Board forums, part of the Community Boards category; Yeah, out of curiousity, what's this graph being used for? Is this your polytope thing from before...

  1. #16
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,066
    Yeah, out of curiousity, what's this graph being used for? Is this your polytope thing from before

  2. #17
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,492
    Quote Originally Posted by MutantJohn View Post
    Yeah, out of curiousity, what's this graph being used for? Is this your polytope thing from before
    Not in the mood for reading the first half of this thread?

  3. #18
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,066
    Uh... I don't think it said anything about what the graph represented, did it? It just seemed like it was about the best way to handle large graphs and then the conversation turned to, "Well, there are two algorithms depending on the nature of the graph." You'll have to excuse me if I find creating a large graph arbitrarily for the sake of traversing it to be rather... I want to say boring but I don't want to mean it. It holds little interest for me and I was wondering if there were any big plans behind it.

  4. #19
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,492
    Quote Originally Posted by MutantJohn View Post
    Uh... I don't think it said anything about what the graph represented, did it? It just seemed like it was about the best way to handle large graphs and then the conversation turned to, "Well, there are two algorithms depending on the nature of the graph." You'll have to excuse me if I find creating a large graph arbitrarily for the sake of traversing it to be rather... I want to say boring but I don't want to mean it. It holds little interest for me and I was wondering if there were any big plans behind it.
    Gah! After my post, did you go back and re-read the entire first half of this thread carefully? The first post didn't mention what it's for, but post #8 just might have. Besides, finding the shortest path from one node to another is not "arbitrary traversal". Regardless of the specific application, there are many interesting use cases you could imagine std10093 using it for (or, if you didn't know anything about it, and thus couldn't imagine, you could have read the links I posted to learn about it's applications): network routing, robotics/path finding, transportation, puzzles solving, video games, etc. No need to apologize though, I don't blame you for finding pointless traversals boring and, well, pointless; just for not reading carefully .

  5. #20
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,066
    You're totally right. Sorry, I walked in to this like half-way and only skimmed. I was assuming it'd stand out more but such are the lessons we learn...

  6. #21
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Since your graph models a social network, you can find nice heuristics to (possibly) increase your speed by orders of magnitude.
    Assume for example, that you need to find the closest relation between two people..
    (So..If (A,B),(B,C),(C,D) are friends, A and D have two in between.)
    Now, instead of plain BFS, if you consider the people in the same geographical area first when putting nodes into your queue, it is likely that you'll have a solution (or one very close to it) very quickly.

    Only when you have tried the standard algorithms and figured that you need a faster solution, should you try these.
    The more clever your heuristic function is, better/faster the results you can count on.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  7. #22
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    I will think that for later. tnx
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 05-02-2012, 06:44 AM
  2. shortest path problem
    By bananorama in forum C Programming
    Replies: 7
    Last Post: 05-24-2011, 12:38 PM
  3. Undirected graph and Binary Tree problem
    By arafat21 in forum C Programming
    Replies: 3
    Last Post: 05-02-2008, 05:52 AM
  4. Shortest path problem
    By Digitalxero in forum C++ Programming
    Replies: 0
    Last Post: 10-25-2005, 05:32 PM
  5. Help!!! Shortest path graph
    By hansy32 in forum C Programming
    Replies: 5
    Last Post: 03-01-2002, 05:39 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21