c++ - Finding shortest circuit in a graph that visits X nodes at least once -

-

even though i'm still beginner, love solving graph related problems (shortest path, searches, etc). faced problem :

given non-directed, weighted (no negative values) graph n nodes , e edges (a maximum of 1 edge between 2 nodes, edge can placed between 2 different nodes) , list of x nodes must visit, find shortest path starts node 0, visits x nodes , returns node 0. there's @ least 1 path connecting 2 nodes.

limits 1 <= n <= 40 000 / 1 <= x <= 15 / 1 <= e <= 50 000

here's example :

enter image description here

the red node ( 0 ) should start , finish of path. must visit blue nodes (1,2,3,4) , return. shortest path here :

0 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0 total cost of 30

i thought using dijkstra find shortest path between x (blue) nodes , greedy picking closest unvisited x (blue) node, doesn't work (comes 32 instead of 30 on paper). later noticed finding shortest path between pairs of x nodes take o(x*n^2) time big nodes.

the thing find circuits eulerian circuit allows visiting each node once (and don't need that). solveable dijkstra or there other algorithm solve this?

here solution fast enough:
1)run shortest path search algorithm every blue node(this can done in o(x * (e log n))) compute pairwise distances.
2)build new graph 0 vertex , blue vertices only(x + 1 vertices). add edges using pairwise distances computed during first step.
3)the new graph small enough use dynamic programming solution tsp(it has o(x^2 * 2^x) time complexity).


Comments

Post a Comment

Popular posts from this blog

database - VFP Grid + SQL server 2008 - grid not showing correctly -

-
i having problem, have grid called "gridbasica" , this: thisform.gridbase.recordsource = "sgviemp" sgviemp cursor made executing select sqlserver command sqlexec. when want modify registry, go form , the update there. so, when come form grid, grid isnt grid anymore, big white rectangle. reading around said: delete recordsource , asingt again. thisform.gridbase.recordsource = "" *--i sqlexe here thisform.gridbase.recordsource = "sgviemp" i , works, but, when click button modify again cursos updated modify form doesnt load fields did first time. could me out that? thanks in advance. --------------- edit ------------------ i have been doing recommended: lnselect = select(0) n = sqlexec(thisform.conexion,"select emp_ccodigo codigo, emp_cnombre 'nombre o razon social', emp_cnumrif 'r.i.f' sgviempr","sgviemp1") set echo on suspend select sgviemp zap in sgviemp *-- browse *--zaps correct
Read more

jquery - Set jPicker field to empty value -

-
im using jpicker color selector in form. have clear value set window/icon 'no color selected' state. i've tried following: $(':input[name="color"]').val(''); //access value directly. (does not affect jpicker) 2: $.jpicker.list[0].color.active.val('hex', '', this); //set color black , input value 000000, instead of empty string 3: $.jpicker.list[0].color.active.val(null, '', this); //does nothing none of 3 methods seems behave properly. in advance. this works me :) $.jpicker.list[0].color.active.val('v', null); here example: http://jsfiddle.net/3up7n/
Read more

.htaccess - htaccess convert request to clean url and add slash at the end of the url -

-
ok , searched more 4 days , more 20 posts here in stach or in websites without kind of success first here htaccess file rewriteengine on rewriterule ^([a-za-z0-9_]+)/?$ index.php?page=$1 [nc] rewriterule ^([a-za-z0-9_]+)\/([a-za-z0-9_]+)\/?$ index.php?page=$1&action=$2 [nc] i tried many codes 1 worked me can call request , works me www.example.com/pagename => www.example.com/index.php?page=pagename here questions , please provide me information "in detail" understand code well 1- how convert request automatically www.example.com/index.php?page=pagename www.example.com/pagename 2- if tried add slash @ end shows me page without images or styling mean www.example.com/pagename => works www.example.com/pagename/ => doesn't work that's :) for first part need 301 rule this: rewritecond %{the_request} /index\.php\?page=([^\s&]+) [nc] rewriterule ^ /%1? [r=301,l] for second part use absolute path in css, js, images files r
Read more