## Single Source Shortest Path

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.
1. 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)
1. 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)
1. 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)