prodipdatta7's blog

By prodipdatta7, 4 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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