Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Graph theory: finding all paths

shortest path

  • Please log in to reply
3 replies to this topic

#1 Squeezy

Squeezy

    CC Lurker

  • Just Joined
  • Pip
  • 1 posts

Posted 28 December 2008 - 06:07 AM

Good day, everyone!
Looks like I really need your help with my work on data structures. The task goes as follows:

For a given unweighted oriented graph G and two its vertices v' and v'', compute
- the shortest path between v' and v''
- (two tasks) all the possible paths between v' and v'' so that paths from any pair do not cross
a) with edges,
B) with vertices.


The first problem is obviously solvable by Breadth-First Search algorithm but I cant seem to puzzle out the second one.
Seemingly it's a recursion involving dynamic programming methods; ideally the solution should expand BFS. Perhaps there are already existing algorithms for that?..

Thanks in advance for any help!
  • 0

#2 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 28 December 2008 - 06:20 AM

I would start by finding all paths that satisfy that property with respect to themselves:
IE find all paths such that the do not self-cross on vertices/edges.
Once that is done, you should have a reasonable space to search from.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#3 $AP

$AP

    CC Newcomer

  • Just Joined
  • PipPip
  • 24 posts

Posted 05 January 2009 - 07:30 AM

all the possible paths between v' and v'' so that paths from any pair do not cross
a) with edges,
B) with vertices.


What does this actually mean? Is it the fact that in the path no vertices/edges occur twice? Then it can easily be done, as you mentioned, exploring BFS and using DP.
  • 0

#4 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 05 January 2009 - 08:04 AM

He's talking about two different problems, one is the set of edge distinct paths, the other is the set of vertex distinct paths (excluding v' and v'')
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/






Also tagged with one or more of these keywords: shortest path

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download