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(N3) Yes
Bellman Ford O(N2) 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.