Thread: breath first search shortest path

  1. 06-10-2010 #1
    iamnew
    iamnew is offline
    Registered User
    Join Date
    Apr 2010
    Posts
    50

    breath first search shortest path

    Why is the breath first search algorithm is considered to be the most efficient shortest path algorithm for unweighted graphs?

    Please help.
  2. 06-10-2010 #2
    KBriggs
    KBriggs is offline
    Registered User
    Join Date
    Jun 2009
    Posts
    486
    I bet google and wikipedia know the answer

    http://en.wikipedia.org/wiki/Breadth-first_search

    Near the bottom
  3. 06-10-2010 #3
    iamnew
    iamnew is offline
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    anyone else knows the answer? Please help. I am a noob in this field.
  4. 06-10-2010 #4
    Elysia
    Elysia is offline
    C++まいる！Cをこわせ！
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Probably because it uses a local greedy algorithm. I only know of the Depth-first search besides this one (for non-negative graphs), but it uses backtracking, which obviously is slower.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
« Previous Thread | Next Thread »
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Shortest path algorithm with a maximum number of edges limit
    By blackslither in forum C Programming
    Replies: 4
    Last Post: 12-28-2008, 04:49 PM
  2. changing the gcc standard include search path
    By RoshanX in forum Linux Programming
    Replies: 1
    Last Post: 01-01-2007, 09:23 AM
  3. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 02:56 PM
  4. Firefox and Google Search
    By DeepFyre in forum Tech Board
    Replies: 0
    Last Post: 01-16-2005, 10:28 AM
  5. Simple search program
    By colinuk in forum C Programming
    Replies: 6
    Last Post: 12-18-2004, 01:58 AM