Shortest path

This is a discussion on Shortest path within the Tech Board forums, part of the Community Boards category; How to find the shortest paths in undirected graphs? i am confused as the algorithms I have found is for ...

  1. #1
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278

    Shortest path

    How to find the shortest paths in undirected graphs? i am confused as the algorithms I have found is for directed graphs....Can anyone please help?

  2. #2
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by anirban View Post
    How to find the shortest paths in undirected graphs? i am confused as the algorithms I have found is for directed graphs....Can anyone please help?
    You can try Dijkstra's Algorithm, which uses weighted edges. If your graph doesn't have weighted edges, just set the weight for each one to 1.

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  3. #3
    Registered User
    Join Date
    Nov 2004
    Location
    India
    Posts
    515
    You can imagine an undirected graph to be a directed graph having same values in a[i][j] and a[j][i] where a is your adjacency matrix. Then run your favorite algorithm and you will get the answer.
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

  4. #4
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    Thanks i got the answer ..

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Single destination shortest path
    By dpp in forum Game Programming
    Replies: 12
    Last Post: 05-12-2009, 12:01 AM
  2. Shortest Path Maze Solver (Breadth Search Help)
    By Raskalnikov in forum C Programming
    Replies: 5
    Last Post: 04-07-2009, 08:41 PM
  3. 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
  4. shortest path algorithm prob
    By Marrah_janine in forum C Programming
    Replies: 2
    Last Post: 10-14-2007, 10:06 PM
  5. Shortest path problem
    By Digitalxero in forum C++ Programming
    Replies: 0
    Last Post: 10-25-2005, 06:32 PM

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