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 ▸What is an Algorithm?
What is the difference between simplex, half duplex and full duplex?
Describe the operations of an optical disk drive used to read data from an optical disk, such as a CD or DVD.
What is the decimal equivalent of the following sequence of bits, which represents an unsigned binary integer: 1101001. What is the decimal equivalent if the sequence in bits encodes a two’s complement binary integer.