Given a graph with n nodes and m edges, every edge has a passing cost that can be negative, find the minimum distance between node 1 and every other node
We will use the Bellman-Ford algorithm to compute the minimum distance between that start node and every other one, by passing through each edge for a maximum of n times and "relaxing the edge", where possible, to obtain the best path. Also, we will improve the algorithm by using only the nodes that helped us relax a path in the past, the other ones being redundant. This will be done by using a queue and the final algorithm will have an O(n*m) complexity but is much faster in practice.
VS
Related Computing A Level answers
All answers ▸How to manually convert a number from decimal into binary?
One member of a chess club sends a text file saved in Unicode. What meant by the term "Unicode" and why might this be necessary?
Represent the denary number 5.625 as an unsigned binary fixed point number with three bits before and five bits after the binary point.
Describe an advantage of using vector graphics instead of bitmaps to represent images.