java - Modifying Dijkstra's Algorithm to find shortest path with largest weighting -


i'm in need of piece of code finds shortest path between nodes greatest weighting. example, quickest route d, greatest weighting:

  - b- --e      /  \ /        d      \  / \       c - -f

so right shortest abd or acd. once weighting applied, code should choose longest path out of 2 (counter-intuitive, huh?).

i'm trying modify algorithm dijkstra's algorithm, end traversing entire graph. know how this? algorithm can code myself immensely.

  1. run bfs source (let s) on graph find length of shortest path s target t, let d. mark d(s,v) - distance s node v.
  2. create subgraph g'=(v',e') of g such that: v in v' if distance source (s) @ d - d(s,v) <= d. e=(u,v) in e' if: both u , v in v'.
  3. create new graph g*=(v*,e*), v'=v*, , edge (u,v) in e* if in e' , d(s,u) < d(s,v).
  4. set new weight function w*(u,v) = -w(u,v), , run bellman ford on g* using w*.
  5. the heaviest shortest path in g s t of weight -d(t), , path found bf matching one.

time complexity of algorithm o(ve), since bellman-ford bottleneck.

correctness proof

claim 1: shortest path s t not contain cycles.
proof simple removing cycle shorter path.

claim 2: shortest paths s t in g'
proof: since shortest paths s t of length d, , eliminated nodes distance s longer d, remove nodes not needed shortest paths.

claim 3: shortest paths s t in g*.
proof: assume removed edge (u,v) in shortest path, , let path s->...->x->u->v->y->...->t. note path v->y->..->t of length d-d(s,u)-1 (assuming d(s,u) minimal)
however, note construction of e*, d(s,v) <= d(s,u) (otherwise (u,v) wouldn't have been removed). so, there path s->...->v->y->...->t distance s: d(s,v) + d-d(s,u)-1 <= d(s,u) + d - d(s,u) -1 <= d-1 - contradiction minimality of d.

claim 4: there no cycles in g*.
proof: assume there cycle in g*: v1->v2->vk->v1. definition of g', nodes reachable s. without loss of generality, let assume d(s,v1) minimal other d(s,vi) (otherwise rotate indices match assumption). there path v1->v2->...->vk->v1, , d(s,v1)=d(s,v1). means @ least 1 edge (vi,vi+1) in path, d(vi) >= d(vi+1) - contradicting construction of e*, , cycle not exist in g*.

claim 5: algorithm correct.

from correctness of bellman-ford, , since g* not contain negative cycles (no cycles @ all), bf find path minimal weight according w* in g*. path 1 maximal weight according w, construction of w*.
since shortest paths in g exist in g* (and them), path shortest path in g maximal weight.

qed


Comments

Post a Comment

Popular posts from this blog

Magento/PHP - Get phones on all members in a customer group -

i working on custom magento extension. working around adminhtml part , i've created custom form there. here form code: <?php class vivasindustries_smsnotification_block_adminhtml_sms_sendmass_edit_form extends mage_adminhtml_block_widget_form { public function _preparelayout() { $extensionpath = mage::getmoduledir('js', 'vivasindustries_smsnotification'); $head = $this->getlayout()->getblock('head'); $head->addjs('jquery.js'); $head->addjs('vivas.js'); return parent::_preparelayout(); } protected function _prepareform() { $form = new varien_data_form(array( 'id' => 'edit_form', 'action' => $this->geturl('*/*/save', array('id' => $this->getrequest()->get...
Read more

php - Bypass Geo Redirect for specific directories -

i'm trying bypass redirect specific url within site. wondering if might able help. the code below code use, original urls replaces example.com i'd able access http://example.com/admin without redirect occuring. is there way this, , there way using own ip? function country_geo_redirect() { $country = getenv('http_geoip_country_code'); if ($country == "us" ) { wp_redirect("http://usa.example.com/"); exit; } else if ($country == "gb" ) { wp_redirect("http://uk.example.com/"); exit; } } add_action('init', 'country_geo_redirect'); you can bypass redirection code if server found ip address. if ip address == <my ip address> ' nothing here else country_georedirect() end if
Read more

php - .htaccess mod_rewrite for dynamic url which has domain names -

i want convert url ex:( example.com/link.php?url=facebook.com ) ( example.com/facebook.com.php ) how can using .htaccess. or there other process make job easier ? i tried adding script .htaccess file options +followsymlinks rewriteengine on rewriterule url-(.*)\.htm$ link.php?url=$1 but converting url adding "url-" ( example.com/url-facebook.com.php ) i want remove "url-" , want make ( example.com/facebook.com.php ) rewriteengine on rewritecond %{the_request} ^get.*link\.php\?url\= [nc] rewritecond %{request_uri} !/system/.* [nc] rewriterule (.*?)link\.php\?url\=/*(.*) /$1$2 [r=301,ne,l] not sure how above work edit of used use remove index.php url
Read more