Graph Shortest Path

Dijkstra's algorithm:
- solves the single-source shortest-paths problem in edge-weighted digraphs with non-negative weights
 using extra space proportional to V and time proportional to E log V (in the worst case).

DAG: (acyclic edge-weighted digraph)
1. Single-source shortest paths: O(E + V)
- solves the single-source problem in linear time.
- handles negative edge weights.

2. Single-source longest paths: O(E + V)
3. Critical path method:

Shortest paths in general edge-weighted digraphs:
- the concept of a shortest path is meaningless if there is a negative cycle.
Bellman-Ford:
- solves the single-source shortest-paths problem from a given source s
- finds a negative cycle reachable from s
- time proportional to E V and extra space proportional to V