Apply Dijkstra's algorithm in a undirected graph with negative weights -


can apply dijkstra's algorithm in undirected graph negative weights above? if algorithm fails.

adjancency's list:

a -> (b, 3), (c, 2), (d, 4) b -> (a, 3), (c, -2), (f, 6) c -> (a, 2), (b, -2), (e, 5) d -> (a, 4), (e, 3), (f, 2) e -> (c, 5), (d, 3), (f, -2) f -> (b, 6), (d, 2), (e, -2) 

seed traversal list source node a, , it's cost 0. add infinite cost every other node:

{}, [a=0, b=inf, c=inf, d=inf, e=inf, f=inf] 

then take lowest current cost item (i'll call l) , "accept" final cost set (the first pass case has l=source node (a), cost of 0). check each edge l calculating total cost follow edge. if total cost less traversal list current cost, update traversal list new lower cost.

{a=0}, [b=0+3, c=0+2, d=0+4, e=inf, f=inf] 

c lowest cost node in traversal list, accept c cost of 2:

{a=0, c=2}, [b=2-2=0, d=4, e=2+5=7, f=inf] 

it's easy detect problem @ point because put cost in traversal list less less cost of node accepted (c). but, unencumbered reason or logic carry on:

{a=0, c=2, b=0}, [d=4, e=7, f=0+6] {a=0, c=2, b=0, d=4}, [e=7, f=6] {a=0, c=2, b=0, d=4, e=7}, [f=7-2=5] {a=0, c=2, b=0, d=4, e=7, f=5} 

due negative cost loops in graph, correct final cost array should be:

{a=-inf, b=-inf, c=-inf, d=-inf, e=-inf, f=-inf} 

but knew dijkstra's fails when graph has negative cost loops...right?


Comments

Popular posts from this blog

html - How to style widget with post count different than without post count -

How to remove text and logo OR add Overflow on Android ActionBar using AppCompat on API 8? -

IIS->Tomcat Redirect: multiple worker with default -