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.