Algorithms For Dummies

 

»

The Dijkstra shortest-path algorithm works only with edges having positive 

weights. (Negative weights will cause the algorithm to loop around some 

nodes indefinitely.)

Demonstrating that a greedy algorithm works the best is a hard task, requiring a 

solid  knowledge  of  mathematics.  Otherwise,  you  can  devise  a  proof  in  a  more 

empirical way by testing the greedy solution against one of the following:

 

»

Against a known optimal solution, when the greedy algorithm produces the 

optimal solution or you can change such a solution by exchanging its ele-

ments into an equivalent best solution (without any loss of performance or 

success). When a greedy solution matches the result of an optimal solution, 

you know that the greedy solution is equivalent and that it works best (this is 

the exchange proof).