# Shortest Path Problem

## Single-source shortest paths

If the graph contains no negative-weight edges, we can apply the GreedyMethod

Dijkstra’s algorithm:

``````Dijkstra(G,w,s):
Set d[s] = 0 and set d[v] = +infinity for all v != s.
Add all the vertices to Q.
while Q is not empty:
u = EXTRACT-MIN(Q)
for each each uv:
d[v] = min(d[v], d[u] + w(u,v))
return d``````

Note: Time complexity: O(v^2)

BellmanFord’s algorithm:

if the graph contains negative edges and under the assumption that there are no negative-weight cycles in the graph

``````BellmanFord(G,s,w):
Set d[s] = 0 and set d[v] = +infinity for all v != s.
// Relax all edges |V| - 1 times. A simple shortest path from src to any other vertex can have at-most |V| - 1 edges
for i = 1 to V-1
for each each edge uv in G:
d[v] = min(d[v], d[u] + w(u,v))
return d``````

Note: Time complexity: O(VE)

### All-pairs shortest paths problem

FloydWarshall algorithm

finding shortest paths in a directed weighted graph with positive or negative edge weights (but with no negative cycles)

``````FloydWarshall(w):
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each vertex v
dist[v][v] ← 0
for each edge (u,v)
dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] ← dist[i][k] + dist[k][j]
end if``````

Note: Time complexity: Θ(v^3)