Graph Algorithm

Shortest Path Problem:
1. Bellman-Ford Algorithm: solves the single-source shortest-paths problem for weighted directed graphs in which edge weights may be negative. It can detect negative cycles and report their existence, but it can not produce a correct answer if a negative cycle is reachable from the source.
Wiki: Bellman-Ford Algorithm
2. Directed Acyclic Graph (DAG): relax the edges according to a topological sort of vertices. The application of this algorithm is to determine the critical path, which is a longest path through the DAG.
3.Dijkstra's Algorithm: solves the single-source shortest-paths problem for weighted directed graphs in which all edge weights are nonnegative.
Wiki: Dijkstra's Algorithm
Longest Path Problem: NP-complete problem.
Wiki: Longest Path Problem
For a DAG,
1) can be solved in polynomial time by negating the edge weights and running a shortest-path algorithm.
2) can be solved in linear time using dynamic programming via a topological sort.