- Time complexity:
- Best: O(V) (when there are no negative edges and the shortest path is found in the first iteration)
- Average: O(V)
- Worst: O(V x E)
- Worst: O(V x E) (when all edges need to be relaxed in every iteration)
- Space complexity: O(V) (storing distances and predecessors)
graph LR
A -->|4| B
A -->|2| D
B -->|2| C
B -->|3| D
B -->|3| E
D -->|1| B
D -->|6| C
D -->|4| E
E -->|-5| C
graph LR
A -->|4| B
A -->|2| D
B -->|2| C
B -->|3| D
B -->|3| E
C -->|4| D
D -->|1| B
D -->|4| E
E -->|-9| C