What is Single Source Shortest Path? Find the shortest paths from a source s to all other vertices v in graph G

- First, we can argue that there is no negative, positive, or 0 weight cyclic path (cycle) in the shortest paths found. Therefore, the paths can contain at most V-1 edges.

**Bellman-Ford algorithm**: the edge weight can be negative and there could be a negative cycle in the graph. If there is a negative cycle that can be reached from the source s, then it returns False. Otherwise, it returns True.

- The algorithm is based on the fact that, for the path p = {v0,v1,v2,…,v_k} from source vertex v0 to v_k, if only (v0,v1), (v1,v2),…,(v_{k-1},v_k) are relaxed in such order, though mixed with other operations, then v_k.d will be the shortest distance from s to v_k.

Bellman-ford(G,w,s): Initialize-single-source(G,s) for i = 1 to G.V - 1: for each edge (u,v) in G.E: //Relax each edge V-1 times Relax(u,v,w) for each edge (u,v) in G.E: //to see if there is a negative cycle if v.d > u.d+w(u,v): return FALSE return TRUE Initialize-single-source(G,s): for each vertex v in G.V: v.d = infinity v.previous = NIL s.d = 0 Relax(u,v,w): if v.d > u.d + w(u,v): v.d = u.d + w(u,v) v.previous = u

- Running time: O(VE)

**Algorithm for directed acyclic graph (DAG).**

DAG-shortest-paths(G,w,s): topologically sort the vertices of G Initialize-single-source(G,s) for each vertex u, taken in topologically sorted order: for each vertex v in G.Adj[u]: Relax(u,v,w)

- Running time: O(V+E)

**Dijkstra algorithm**: for directed graph with non-negative weight edge.

Dijkstra(G,w,s): Initialize-single-source(G,s) S = an empty set Q = G.V while Q is not empty: u = EXTRACT-MIN(Q) S = S.add(u) for each vertex v in G.Adj[u]: Relax(u,v,w)

- Running time: similar to Prim algorithm.
- Array: O(V^2);
- binary heap: O(Vlg(V)+Elg(V));
- Fibonacci heap: O(E+ Vlg(V)).

Sometimes, we can construct a artificial graph and use single source shortest path algorithms to solve the **difference constraints problem**. (The values of vertices satisfy some <= or >= relationship, which can be represented by the value of their edges.)