Temos aqui um problema clássico de grafos, o problema do caminho mínimo, porém com uma interessante modificação: o número de arestas de tal caminho mínimo deve ser par.

Temos então uma condição especial em nossa busca: para toda aresta que eu usar pra procurar o caminho mínimo, terei que usar mais uma para que a soma total seja par. Porém há casos em que esta segunda aresta me afasta do objetivo, e isso faz com que a estratégia se torne confusa.

Para deixarmos essa condição menos confusa podemos reduzir o grafo original a um grafo auxiliar. Neste grafo auxiliar iremos manter todos os vértices do grafo original, porém substituir todas as arestas da seguinte maneira: sejam A, B e C vértices distintos do grafo original, tal que existam uma aresta entre A e B com peso P1, e uma aresta entre B e C com peso P2. Adicionaremos então uma aresta no grafo auxiliar entre A e C com peso P1+P2.

Notem que agora temos um grafo onde cada aresta na verdade representa duas, fazendo com que qualquer caminho neste grafo auxiliar tenha um número par de arestas no grafo original.

Agora que a condição especial foi tratada, basta resolver o problema do caminho mínimo com um algoritmo adequado, tal como o Dijkstra.

Fonte: http://crbonilha.com/