Graph - Update In Progress

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)

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

 Floyd-Warshall algorithm:

• Solve all-pairs shortest path problem.
• Time proportional to V^3 and space proportional to V^2

MST(minimum spanning tree)

• A MST of an edge-weighted graph is a spanning tree whose weight (the sum of the weights of its edges) is no larger than the weight of any other spanning tree.
•