Please enable JavaScript.
Coggle requires JavaScript to display documents.
Bell-Ford and Greedy Algs. - Coggle Diagram
Bell-Ford and Greedy Algs.
Neg. cost shortest pat. prblm.
Resolv. sngl src short pts prblm in the gen. case where neg. edge weights/costs exst.
Eg.
Traversing a nd. in a netw. tht chrg. pkt rting. lss of reven. can be modelled with neg. cost.
neg.- cost cycle
loop tht mks shrts pth btw 2 pts undef.
cycl. only are problmtc.
Bell-Ford alg.
wrks. wth neg. weights
.Detects neg. wghts. - Fnd shrt smpl pth if no neg. cycl exsts
if G = (V,E) cnts neg. weight cycl., some shortest pts mat exist.
slwr thn Dijkstra's alg.
more versatile
Can hndl neg. weigts
psuedcode fnd on sl 8
procedure
init.
src node
to 0 and other
vert - infinity
2.Check
adj nodes to A
and update accordingly
3.Choose
min node
fr proces.
4.Check adj nodes to A
In 2nd iter., chk all nds agn and see whether it is possbl. to reduce the cost of reaching any of the nds.
6.3rd iteration, check all nodes agn to see whethr it is possbl to reduce the cst of reaching any of the other nds.
7.If there is no change in the distance and predeccor array the ith iteration, thn we can immediately terminate the algorithm.
Define greedy alg.
Builds up gradually and makes the best decision at every step, cannot see what the overall best decision is
Min. spanning tree prblm. alg.
1.Prim's alg.
Solves finding an MST
2.Kruskal;s alg,
Define spanning tree
An undir., con. grph. tht is a tree and con.all the vert. of the grph.
A graph can have many spanning trees.
Acyclic graph
a.k.a,forest
Ech. con. nd. in forest is a tree.
Findg. a MST
con. every vertx in a grph.
Proc. for Prims alg.
Select a rand. starng, nod. in grph. Place it in a nw tree, T.
Considr. whch arcs con. nds in T to nds outsd T. Pck 1 with a min wght(if > 1 choose any). Add ths arc and node to T
3.Repeat step 2 until T contns evry nde of the grph
Complexity
Space complexity
O(m+n)
Time complexity
O(m log (n))
Uses a heap-based priority queue
analys. sim. to Dijkstras alg.
Kruskals alg.
