algorithm - Find the minimum weight cycle that contains a specific edge -


given graph: - oriented, - connected , - weighed (the weights positive) have write function taken input edge (u, v), calculate weight of cycle of minimum weight contains edge.

i thought i'd follows procedure inaccurate , incomplete: - starts bfs visit starting node u - keep in variable temporary weight - when arrive v choose minimum of previous weights. how keep track of previous weights? how write pseudocode?

i have no idea how started me?

thanks

this can reduced shortest path problem:

find shortest path v u, shortest cycle contains (u,v), v->...->u->v, v->...->u shortest path v u found shortest path algorithm.

it can solved efficiently using dijkstra's algorithm, since there no negative weights in graph.

correctness proof:

assume there cheaper cycle v1->v2->...vi->u->v->v_i+1->...->vn->v1. let's weights x < d(v,u) + w(u,v)
since it's cycle, can @ v->v_i+1->....->vn->v1->...->vi->u->v.
the weight of cycle didn't change, , still x. means x=w(v,v_i+1) + ... + w(vn,v1) + ... + w(v_i-1,vi) + w(vi,u) + w(u,v)
but gives w(v,v_i+1) + ... + w(vn,v1) + ... + w(v_i-1,vi) + w(vi,u) + w(u,v) - w(u,v) < d(v,u), , have found shorter path v u, d(v,u), contradicting correctness of dijkstra's algorithm.

qed


Comments

Post a Comment

Popular posts from this blog

javascript - Bootstrap Popover: iOS Safari strange behaviour -

i looking through twitter bootstrap documentation, , i'm interested in implementing dismissible popover when button clicked. here example bootstrap's docs: http://getbootstrap.com/javascript/#dismiss-on-next-click when press "dismissible popover" button os x safari browser works fine. when access same link above ios safari, button not work. is, popover not dismissed on click. why button not working ios safari? the example linked using data-trigger="focus" attribute. try changing data-trigger="click" . <a tabindex="0" class="btn btn-lg btn-danger" role="button" data-toggle="popover" data-trigger="click" title="dismissible popover" data-content="and here's amazing content. it's engaging. right?">dismissible popover</a>
Read more

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

session - Logging Out Using PHP -

i have seen other programs regarding can't seem make work. doing wrong? want achieve after user logged out, going previous pages become restricted. i have 3 php files: 1. sample.php - main page username , password filled in 2. successful.php - user's page after logging in 3. logout.php - destorys session hinder user access pages after logging out sample.php </html> <form action="" method="post"> <table> <tr> <td>username:</td> <td>password:</td> </tr> <tr> <td><input type="text" name="username"></td> <td><input type="password" name="password"></td> </tr> <tr> <td><input type="submit" value="submit" name="submit"></td> </tr> </table> </form> </html> <?php $servername = "localhost"; $username = ...
Read more