Bellman–Ford algorithm
It is more robust than Dijkstra's algorithm because it is able to handle graphs containing negative edge weights. It may be improved by noting that, if an iteration of the main loop of the algorithm completes without making any changes, the algorithm can be immediately completed, as future iterations will not make any changes. Its runtime is  time, where  and  are the number of nodes and edges respectively.