Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Odd Graph Algorithm assignment

  1. May 22, 2008 #1
    I've got a small assignment to do on graphs but it's a bit frustrating that no standard algoritms such as Dijkstra, Bellman-Ford, etc. can be used or at least I don't know how could they help.

    Given a graph one is to find shortest path through N points. That's it. Starting point can be anything you like just the path must go trough N distinct points where the path itself should be as short as possible. The graph is weighted, undirected.

    Simple Greedy algorithm works fine for small inputs but when N gets > 100 then it is useless. I'd like to see it work for N > 1000 in resonable time. Sadly I don't see how any of the well known algorithms could be put into practice here. Any ideas, pointers would be greately apprichiated...
     
  2. jcsd
  3. May 22, 2008 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This is essentially the travelling salesman problem.
     
  4. May 23, 2008 #3
    silly me, will look into TSP algorithms, just need to modify not to go trough all the points but just N points. Since the graph can have M points but I am interested in visiting only N points and not all.

    For starters something along the lines of a simple BFS with heuristic to always select shortest neighbor and only visit N nodes should work out fine.

    Sometimes it helps to think out loud.

    I was a bit to eager to try out Dijkstra or Bellman-Ford, can not match an algorithm to a problem, it goes the other way around.
     
    Last edited: May 23, 2008
  5. May 23, 2008 #4
    There is just a slight problem, if I am not mistaken the TSP requires that the graph is complete.

    But my graph is not complete - it is more like railway diagram, where the vertices are train stations and edges are the rails, it is connected but not complete and I want to visit N train stations where my path will be shortest. Any ideas?
     
  6. May 23, 2008 #5

    -Job-

    User Avatar
    Science Advisor

    If your problem is equivalent to TSP then don't bother searching for an efficient (polynomial time) algorithm.

    The problem is similar to TSP, on the other hand i can't think of a polynomial time reduction from TSP to your problem off the top of my head. Until you have a reduction to TSP (or to any NP-Complete problem) it's possible that there is an efficient solution for your problem.
     
    Last edited: May 23, 2008
  7. May 23, 2008 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Nope. But it's easy to show that solving the TSP on an arbitrary graph is equivalent to solving the TSP on a complete graph.
     
  8. May 23, 2008 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The TSP is the N=M case of his problem.
     
  9. May 23, 2008 #8

    -Job-

    User Avatar
    Science Advisor

    That's not sufficient by itself though because supposing we're given a TSP instance with N nodes, if i pass it to a solver of Haki's problem and ask for the shortest sequence of N nodes, then the sequence it returns may not be a hamiltonian cycle - the start and end nodes could be disconnected.

    What else did you have in mind?
     
  10. May 23, 2008 #9
    What if my arbitrary graph is
    6 train stations where the geometric layout is like the 5 stations are at the edges of a 5 pointed star with 6th station being in the center as the hub, and the 5 stations are only connected to the hub station i.e. G({a,b,c,d,e,h},{a-h,b-h,c-h,d-h,e-h}).

    There is no way for the sales person to visit all the stations without going trought the hub 5 times ... but doesn't TSP state that each station should be visited only once? Or am I missing something? Graphs are not my strong point.

    As algorithm goes a pointer for approximation algorithm would be great.
     
  11. May 23, 2008 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Good call; I hadn't realized you were allowing the salesman to return to a node. I still think there is an equivalence, but it's more difficult, and I haven't worked out the details.
     
  12. May 24, 2008 #11
    The salesman should not visit any node more than once.

    In the 5 point star graph, if I'd put it in my problem solver let's say the solver is PS(G,N) where PS is the solver, G is the graph(not-connected, undirected, weighted) and N is the number of stations to visit.

    for PS(G({a,b,c,d,e,h},{a-h,b-h,c-h,d-h,e-h}),2) I'd want it to output any edge, a-h would work fine, for N = 3, I'd want it to output a-h,h-b or any other combination, but for N=4 I'd want it to fail saying there is no path where the salesman would visit 4 stations without revisiting any station more than once.

    Right now I have something in the lines of DFS. I take a random starting point and select next shortest neighbour repeating until the desired number of stations is visited but handling of dead ends is quite poor.

    In the 5 star graph for N=3, if the algorithm starts at the center, it would take next shortest neigbour let say a, so we have first edge h-a, but a is a dead end, so it would go back and select next neighbour b, edge h-b is another dead end, then with c,d and e and then it would finally conclude this is a bad starting point and start with a different starting point. I am sure there is a better way just don't know of it.

    If I could use Lin-Kernighan or something similar that's awesome, but for LK afaik it takes a matrix of distances between any pair of cities, but in my case the shortest distances between 2 cities could require a revisit of already visited city.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Odd Graph Algorithm assignment
  1. Graph algorithm (Replies: 25)

  2. C++ assignment (Replies: 7)

  3. Graph theory algorithm (Replies: 2)

Loading...