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

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

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

url rewriting - How to redirect a http POST with urlrewritefilter -