## Introduction

*Prerequisites*: Graph Theory

The shortest path is defined as a path from one node to another while trying to minimize a certain property (least number of nodes, smallest total weight). However, shortest paths may have negative weights which leads to cycles.

## Implementations

Algorithm | Time | Detect cycles? |
---|---|---|

Floyd Warshall | O(N^{3}) |
Yes |

Bellman Ford | O(N^{2}) |
Yes |

Dijkstra's | O(N log N) | No |

- Floyd Warshall computes the shortest path between all pairs of nodes.
- Bellman Ford computes the shortest path between one node to every other node.
- Dijkstra's computes the shortest path between two nodes.