Algorithm

I use Suurballe's algorithm (look here , here or here).

If you do not know the basic idea of the Suurballe's algorithm, there is no point in reading further!

Structures

To explain the algorithm, I will introduce you to the necessary information for the algorithm about the graph elements with which I will work:

typedef struct	s_node
{
	int	marked;
	int	separate;
	int	marked_sep;
	int	parent;
	int	weight;
	int	in_new_path;
}		t_node;

# define MARKED_IN	0
# define MARKED_OUT	1

• marked : just a flag. 0 - if we didn't visited this node while traverse, 1 otherwise
• separate : just a flag. 1 - if this node separate, 0 otherwise

In fact, this is already an optimization. Most part of students just create new graph when thew split the rooms, and work with it. But I develop a really fast lemin, so I just use flags.

• marked_sep : just a flag. 1 - if we hit in OUT node, 0 - if IN
• parent : parent node - from which we got to this node
• weight : each node has weight. if we go along the positive path - weight + 1; -1 otherwise
• in_new_path : just a flag. 1 - if this node already a part of new path. 0 otherwise

typedef struct	s_connect
{
	int	state;
}		t_connect;

Each connect has its own state:

• POSITIVE - usual and init state
• NEGATIVE - connect from end to start after reverse
• FORBIDDEN - connect from start to end after reverse

Algorithm