algorithm - shortest path between all vertex using bfs -

-

i'm learning graph theory , need help. need algorithm shortest path between vertex in graph using bfs. know how bfs works don't know "remake" algorithm find shortest path between vertex in graph.

the simple way repeated bfs each node, yerken said. time complexity o( (v+e)*v ), v , e number of vertices , edges, respectively. o(1) < e < o(v^2), if graph dense, o(v^3) algorithm. if graph sparse , complexity o(v^2), can done faster repeated dijkstra's, because complexity o(v * e * log(v)) = o(v*log(v)).

alternatively can try floyd-warshall algorithm o(v^3), gives distances, not paths.


Comments

Post a Comment

Popular posts from this blog

sql - invalid in the select list because it is not contained in either an aggregate function -

-
i can't figure out rewrite sql statement avoid error below msg 8120, level 16, state 1, line 26 column 'staffmember.staffmemberid' invalid in select list because not contained in either aggregate function or group clause. sql statment select (select [dbo].[udf_readstaffmemberbasic](sm.staffmemberid) xml path ('staffmembersummary'), root ('items'), type ), count(sm.staffmemberid) totalresults, ceiling(cast(count(sm.staffmemberid) decimal)/ @pagesize) totalpages staffmember sm inner join staffmembertoadditionalrole ar on sm.staffmemberid = ar.staffmemberid (sm.firstname '%' + @name + '%' or sm.surname '%' + @name + '%') , (@floorid null or sm.floorid = @floorid) , (@directorateid null or sm.directorateid = @directorateid) , (@additionalroleid null or ar.additionalroleid = @additionalroleid) order sm.staffmemberid offset @page * @pagesize rows fe...
Read more

Angularjs unit testing - ng-disabled not working when adding text to textarea -

-
i trying test angularjs component using karma, mocha, power-assert. have textarea , button in component, button disabled based on length of text in textarea. when run component in browser works perfectly. can't figure out how test functionality. here's bit of code. inquiryform.js function inquiryform($scope) { // plan add logic here } angular.module('myapp').component('inquiryform', { controller: inquiryform, controlleras: 'inquiryform', templateurl: 'inquiryform.html' }); inquiryform.html <div class="contact"> <div>thanks contacting us.</div> <form> <textarea ng-model="inquiryform.inquirytext" name=""></textarea> <input type="submit" value="send" ng-disabled="!inquiryform.inquirytext.length"> </form> </div> inquiryformtest.js describe('inquiry form ', () => { let $r...
Read more

How to start daemon on android by adb -

-
can me please, head swollen... i trying run daemon on android emu/device command: adb -s <device_name> shell su -c /dir/daemon <port_number> but nothink happens, , no errors! if do: adb -s <device> shell and form shell cmdline: su -c /dir/daemon <port_number> than work fine. try use shell-script , run: adb -s <device_name> shell sh su -c /dir/script.sh <port_number> and try generate script qt code port number , use: adb -s <device_name> shell sh su -c /dir/script.sh but not helped... problem if enter adb shell previous run daemon - work. problem on different device/emu/iso_image different command format not work. example: adb -s <device_name> shell su -c /dir/daemon <port_number> // work @ emu, not @ iso and vice: adb -s <device_name> shell su -c "/dir/daemon <port_number>" // work @ iso etc. everybody can answer what's matter? sorry english adb shell su -c ...
Read more