Given a connected undirected weighted graph of **n (<= 15)** nodes and **m(<= 1000)** edges.

Every edge is assigned a positive integer which is the length of the edge.

In this graph i need to make the degree of every node even by adding some fake edges between nodes.

The cost of adding a fake edge is the length shortest path between this nodes in the initial graph.

It is obvious that i can use floyd warshall algorithm to compute the shotest path between every pair of nodes. < br> How can I add fake edges with minimum cost ?

Actually this is needed as a sub-problem of another problem i'm trying to solve but can't afford an efficient way.

link: 1086 — Jogging Trails

Your any kind of help will be cordially accepted.

Thanks.

Auto comment: topic has been updated by prodipdatta7 (previous revision, new revision, compare).Auto comment: topic has been updated by prodipdatta7 (previous revision, new revision, compare).