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
Post a Comment