graph - Does Dijkstra's algorithm give shortest path always? -

-

i learning dijkstra's algorithm , had basic query. have graph looks follows..(non-negative nodes):

a---2-----b------16------d-----3-------f
* *
* *
3 4
* *
c----------2---------------------------e

not clear above graph display, ac has distance of 3 , ef has distance of 4.

i interested in finding shortest path between , f.

consider destination node f. when consider nearest node, d (df has weight 3 , ef 4). however, when follow path, shortest path as: a,b,d,f (total distance: 19).

a quick observation tells shortest path a,c,e,f (distance: 9). however, since in 1st step, e more distant d, followed d.

am missing here? dijkstra's algorithm not showing right result here.

yes dijkstra's gives shortest path when edge costs positive. however, can fail when there negative edge costs.


Comments

Post a Comment

Popular posts from this blog

java - WrongTypeOfReturnValue exception thrown when unit testing using mockito -

-
my test list<person> mylist; @test public void testisvalidperson() { mylist = new arraylist<person>(); mylist.add(new person("tom")); when(persondao.get(person)).thenreturn(mylist); when((persondao.get(person)).isempty()).thenreturn(false);//------exception thrown boolean result = service.isvalid("tom"); assertfalse(result); } method tested: public boolean isvalid(string person){ persondao = new persondao(); person personobj = new person(person); return (persondao.get(person).isempty())?false : true; } exception thrown: org.mockito.exceptions.misusing.wrongtypeofreturnvalue: boolean cannot returned get() get() should return list *** if you're unsure why you're getting above error read on. due nature of syntax above problem might occur because: 1. exception *might* occur in wrongly written multi-threaded tests. please refer mockito faq on limitations of concurrency testing. 2. sp...
Read more

c++11 - Intel compiler and "cannot have an in-class initializer" when using constexpr -

-
the following test program compiles , runs fine g++. intel icpc (14.0.2) compile , run if use explicit type double instead of template. template version icpc produces error: icpc -g -o2 -i. -std=c++0x -c main.cc -o main.o main.cc(10): error: member of type "const t [9]" cannot have in-class initializer static constexpr t dx_[9] = { test code template<typename t> class myclass { public: static constexpr t dx_[9] = { 1.5, 2.0, -0.5, -0.5, 0.0, 0.5, 0.5, -2.0, -1.5 }; }; template<typename t> constexpr t myclass<t>::dx_[9]; int main(int argc, char *argv[]) { return 0; } // main why receiving error "cannot have in-class initializer" when using constexpr ? this bug of intel compiler, submitted intel , fixed in future versions. also see multiple constexpr bugs , sfinae bug intel c++ compiler 15 , method constexpr bug c++ compiler 15 on intel forums.
Read more

symfony - imagine_filter() not generating the correct url in LiipImagineBundle -

-
i think there bug in bundle liipimaginebundle. explain: here new config of bundle: liip_imagine: resolvers: default: web_path: web_root: %kernel.root_dir%/../web/img # %kernel.root_dir%/../web/img folder filtered images created! cache_prefix: media/cache # media/cache prefix of folder cached images created filter_sets: cache: ~ my_thumb: quality: 75 filters: thumbnail: { size: [120, 90], mode: outbound } this twig part displaying image: {# way filtered image not created!#} <img src="{{ 'img/test.jpg' | imagine_filter('my_thumb') }}" /> {# way, filted images created. asset() must used. #} <img src="{{ asset('img/test.jpg' | imagine_filter('my_thumb')) }}" /> the generated link of image not correct! in fact, obtained link is: http://localhost/media/cache...
Read more