algorithm - Finding the shortest path in a colored graph -


the problem trying solve is:

given graph each edge colored in either red or blue:

a) give algorithm produces path between 2 vertices (s,t) goes on minimal amount of red edges.

b) give algorithm produces path between 2 vertices (s,t) goes on minimal amount of blue edges, out of paths go s t pass through minimal amount of red edges.

so far: a) can use modified bfs algorithm. when looking @ vertex, v, put vertices connected blue edge v first in queue, , add rest end of queue. thus, first time algorithm encounter t path in question.

how prove correctness of algorithm? seems greedy. how expand answer b)?

thanks time.

there 2 important details algorithm need keep in mind:

  1. nodes can added queue multiple times in scenario. allowed explore them once, though. can enforce maintaining boolean flag per node tells whether have explored node.
  2. you can stop algorithm take t out of queue, not put in.

if way (and question doesn't indicate don't), algorithm indeed correct.

how prove correctness of algorithm?

if assign edge weight 1 red edges , edge weight 0 blue edges, problem reduces find shortest path in transformed graph. let's apply dijkstra problem. show algorithm in fact implements dijkstra, proves correctness.

we can show ever have nodes of 2 different distances in priority queue: if m minimum distance of node in priority queue, can't have node of distance m + 2 in queue, because mean must have explored node distance m + 1, impossible because explore nodes in order of increasing distance.

your modified bfs in fact implements dijkstra algorithm using double-ended queue 2-value priority queue: if q queue, there index i, such q[1..i] contains nodes of distance m , q[i+1..] contains nodes of distance m + 1.

how expand answer b)?

you can extend concept maintaining 4-value priority queue, example implemented 2 double-ended queue. 1 queue hold nodes of distance m red edges, other hold nodes of distance m + 1 red edges. both ordered increasing number of blue edges (there 2 different distance values in each of these).


Comments

Post a Comment

Popular posts from this blog

php - SPIP: From Tag directly to an article -

i work spip , plugin called tagsphere works fine tags in spip. have tag groupe put 1 article tag. when click on tag in tagsphere send me before menu can see articles linked tag. want send me directly article without see tag menu before. here code model of thagsphere: <div id="tagsphere-#env{id_article}"> <ul> <boucle_mot(mots){id_groupe ?}> <li>[<a href="#url_mot">(#titre)</a>]</li> </boucle_mot> </ul> </div> anybody idea? if want skip tag page, have link directly article. <b_article> block prevents display tag if no article linked. <div id="tagsphere-#env{id_article}"> <ul> <boucle_mot(mots){id_groupe ?}> <b_article> <li> <a<boucle_article(articles){...
Read more

jquery - isAjaxRequest always return false -

i got error message 404,'model has not been saved' following code my action controller public function actionextend($id) { $model=$this->loadmodel($id); if(yii::app()->request->isajaxrequest) { $model->todate = date('y-m-d h:i:s a',(strtotime('next month',strtotime(date('y-01-d'))))); if($model->save()) { yii::app()->end(); } else { throw new chttpexception(404,'model has not been saved'); } } } the jquery call $("#buttonextend<?php echo $this->post_row;?>").click(function(e){ $.ajax({ type: "post", url: "<?php echo yii::app()->createurl('post/extend', array('id' => $data['id'])); ?>", }); }); why not ajax call ? thank help i found response, missed } , function ...
Read more

ruby on rails - In a controller spec, how to find a specific tag in the generated view? -

i know integration tests preferred need ran in controller test, i'm testing gem injecting html code in view, xhr can't run in feature spec (if can, please explain me how :) ) so rspec controller tests can assert selector present (with capybara) : response.body.should have_selector('#foobar') has_selector? call all method capybara find selector. what want last child of body , assert id in particular. afaik it's not possible have_selector. what : all('body:first-child').first.id.should == '#foobar' however, capybara dsl, defined (more or less): def all(*args) page.all(*args) end and page empty unless use visit it's integrations specs. how can use capybara all method inside rspec controller test ? i can't test right after googling seems trick def page capybara::node::simple.new(response.body) end source
Read more