Results 1 to 3 of 3

Thread: Lowest-cost cycle passing all edges at least once

  1. #1
    Apr 2009

    Lowest-cost cycle passing all edges at least once

    I've been trying to figure out the solution to the following problem for a number of hours now:

    "Attached to this post is a weighted graph. Find a cycle (same start and end point) through the graph so that each edge is passed at least once, and so that the weight sum is minimal".

    We've recently been learning about Dijkstra's algorithm but I can't see if and how it could be applied here as we have to pass every edge. The solution I've come up with so far is to start from either b or f , and "eliminating" the b-f edge by going back and forth once. By doing so, the rest of the graph is an Euler graph and we can find a cycle that passes each edge exactly once. If my calculations are correct, the weight sum becomes 39. However, what concerns me is that the b-f edge has the highest weight and that there may therefore be a better (systematic?) solution to the problem.

    Any ideas greatly appreciated. Thank you.
    Attached Thumbnails Attached Thumbnails Lowest-cost cycle passing all edges at least once-graph.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    May 2009
    Tokyo, Japan
    This seems to be quite an NP complete problem, meaning that there is no algorithm that solves the problem in polynomial time. What you might be able to do however is just make a simple searching algorithm that searches through the whole space, starting with the next edge so that the total value of the current path is the smallest. the first answer it finds is then your solution. Starting point is arbitrary as you have to find a cycle.
    I doubt any closed form complete fast algorithm exists for this problem, so that might be your best bet.

    I think you might be completely right though, and just following the euler cycle with the added 5 from getting back to the starting point is the fastest way to go. This seeing as you have to go back one edge from any of the uneven edged vertices anyway, but instead of b f you go b e a b, which is 4 long instead of 5.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Apr 2009
    Thanks for the help. I had to hand in the assignment but I'll continue looking for a way to prove (or review) the solution.

    P.S. Where in Tokyo are you studying? I'm currently on an exchange year there myself.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Jul 30th 2010, 10:01 AM
  2. Process cost systems,total cost under the FIFO Method.
    Posted in the Business Math Forum
    Replies: 0
    Last Post: Dec 4th 2009, 11:13 PM
  3. Marginal Cost/Demand and Cost
    Posted in the Calculus Forum
    Replies: 4
    Last Post: Nov 4th 2009, 06:45 PM
  4. Replies: 5
    Last Post: Jun 22nd 2008, 10:20 PM
  5. Replies: 2
    Last Post: Dec 9th 2007, 02:33 PM

Search Tags

/mathhelpforum @mathhelpforum